算法系列——JavaScript快速排序思想实现

lentrue 发布于2019-08-21 17:33 / 2446人阅读

摘要：源码实现快速排序理论理解起来很容易，但经常是实际写代码，无从下手，下面是我根据快排的步骤实现的递归快速排序。合并第一次快速排序的，，数组。

原理

快速排序离不开递归的思想，你如果不了解递归，可以结合我另外一篇文章来学习算法入门之递归分而治之思想的实现

网上有有趣的动态图来表示快速排序，但其实我们大部分程序员都是脑子不太好使那种，即使看了形象生动的动态图，还是想不到具体实现思路。

排序都有基本的步骤，快排也不例外，通常分为这么几步：

1、选择基准值；

2、需要2个空数组，分别位于基准值的左边和右边，小于基准值的push到左边的数组，大于基准值的push到右边的数组；

3、递归重复上面的步骤。

具体思路分析

原始数组	[2, 4, 1, 5, 3, 1]
找基准值 base	末尾元素1
拆分	left [1] <- [base] -> [2, 4, 5, 3] right
递归	对left和right的数组重复第一步找新的基准值
模拟递归1	[1], [1], [2] <- [3] -> [4, 5]
模拟递归2	[1], [1], [2], [3], [4] <- [5] -> []
递归结束，合并数组	[...[1], ...[1], ...[2], ...[3], ...[4], ...[5]]

这个表格模拟快速排序的具体步骤，递归是将一种规律重复执行N次的操作，我们找到快速排序的规律，然后return 递归，当递归到数组为1个元素时，不再递归，因为只剩一个元素的数组不需要再比较了。

JavaScript源码实现快速排序

理论理解起来很容易，但经常是实际写代码，无从下手，下面是我根据快排的步骤实现的递归快速排序。qSort函数不复杂，他表示执行一次找基准值并且遍历比较的过程，而你可能不太理解的是函数最后面的return。

return [...qSort(left), ...[base], ...qSort(right)]

将这个return拆分开来看。

1、返回值应该是个数组。

return []

2、合并第一次快速排序的left，base，right数组。接着就交给递归去执行左边和右边数组的排序。

return [qSort(left), [base], qSort(right)]

3、因为qSort返回的是数组，不是数组元素，所以需要用ES6语法...来散列开。

完整代码：

function qSort(arr) {
  //声明并初始化左边的数组和右边的数组
  var left = [], right = []
  //使用数组最后一个元素作为基准值
  var base = arr[arr.length - 1]
  //当数组长度只有1或者为空时，直接返回数组，不需要排序
  if(arr.length <= 1) return arr
  
  //进行遍历
  for(var i = 0, len = arr.length; i < len - 1; i++) {
    if(arr[i] <= base) {
    //如果小于基准值，push到左边的数组
      left.push(arr[i])
    } else {
    //如果大于基准值，push到右边的数组
      right.push(arr[i])
    }
  }
  //递归并且合并数组元素
  return [...qSort(left), ...[base], ...qSort(right)]
}
const arr = [2, 4, 1, 5, 3, 1]
const s = qSort(arr)

console.log(s) // [1, 1, 2, 3, 4, 5]

时间复杂度

快速排序的平均时间复杂度是O(nlogn)，最差情况是O(n²)。

云服务器 GPU云服务器快速排序算法最好的快速排序算法最快速的排序算法 javascript编程思想

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/89668.html

JavaScript 数据结构与算法之美 - 归并排序、快速排序、希尔排序、堆排序

摘要：之所以把归并排序快速排序希尔排序堆排序放在一起比较，是因为它们的平均时间复杂度都为。归并排序是一种稳定的排序方法。因此，快速排序并不稳定。希尔排序思想先将整个待排序的记录序列分割成为若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言算法为王。想学好前端，先练好内功，只有内功深厚者，前端之路才...

haitiancoder 2019-08-26 10:20 评论0 收藏0
JavaScript 数据结构与算法之美 - 桶排序、计数排序、基数排序

摘要：之所以把计数排序桶排序基数排序放在一起比较，是因为它们的平均时间复杂度都为。动画计数排序思想找出待排序的数组中最大和最小的元素。桶排序计数排序能派上用场吗手机号码有位，范围太大，显然不适合用这两种排序算法。 showImg(https://segmentfault.com/img/bVbuF9e?w=900&h=500); 1. 前言算法为王。想学好前端，先练好内功，只有内功深厚者...

Awbeci 2019-08-26 10:24 评论0 收藏0
算法系列——JavaScript中广度优先搜索思想实现

摘要：散列表上面的地图向我们展示了如何用广度优先搜索的思想找到北京到广州的最短路线。在广度优先搜索中，我们需要用到队列的这种思想来实现查找。建立了下面这个模型武汉广州西藏上海上海武汉广州代码完整实现，利用递归和广度优先搜索的思想实现。什么是广度优先搜索？如果只是是背概念，幼儿园的小朋友都能背下来念给你听。假设看这篇文章的都和我一样是个前端工程师，我们要从广度优先搜索（BFS）中学到什么...

everfly 2019-08-21 17:36 评论0 收藏0