脚本宝典收集整理的这篇文章主要介绍了

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

脚本宝典小编觉得挺不错的,现在分享给大家,也给大家做个参考,希望能帮助你少写一行代码,多一份安全和惬意。

原理

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

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

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

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²)。

总结

以上是脚本宝典为你收集整理的

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

全部内容,希望文章能够帮你解决

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

所遇到的程序开发问题,欢迎加入QQ群277859234一起讨论学习。如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典网站推荐给程序员好友。 本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。

80%的人都看过