黑马程序员技术交流社区

标题: 快速排序 [打印本页]
作者: 绮罗    时间: 2020-5-13 17:28
标题: 快速排序
手写算法并记住它：快速排序（5行代码简单版）
对于经典算法，你是否也遇到这样的情形：学时觉得很清楚，可过阵子就忘了？
本系列文章就尝试解决这个问题。
研读那些排序算法，细品它们的名字，其实都很贴切。
比如快速排序，一个快字就能体现出其价值，因而它是用得最多的。
因为它相对难一些，本系列将分两篇文章讲解它。
本篇是一种简单实现版本，与归并排序做对比，摸清快排的总体思路。下一篇才是常见于各教程中的原地排序算法。
快速排序这个名字是针对其性能来起的，但很难让人做到见名知意。
所以，我给它重新起了个名字：归分排序。
与归并算法一样，归分算法也是分而治之算法，讲究分、归、并。前者的重头戏在于如何去合并，后者的重头戏在于如何去划分。


上图中，先把数组按最后一个元素4作为分界点，把数组一分为三。左子部分全是小于等于4的，右子部分全是大于4的，它们可以进一步递归排序，最后合并这三部分。
其中，并和归相对容易些，该算法的核心是：如何把数组按分界点一分为三？
这一点对于我们JSer来说，非常容易，使用filter就能做到：
let pivot = array[array.length - 1]let left = array.filter((v, i) => v <= pivot && i != array.length -1)let right = array.filter(v => v > pivot)[color=rgba(140, 140, 140, 0.8)]复制代码
其中left部分要排除掉分界点元素，因此要求不能是最后一个。
分，这个核心问题解决了，接下来我们来看看并和归。
关于并，要拼接三个数组，在JS中都有相应的API（比如concat），这里我们简单实用展开运算符即可：
let result = [...left, pivot, ...right][color=rgba(140, 140, 140, 0.8)]复制代码
至于递归，虽然它不符合线性思维，但其实也没啥难的。
只要有递归步骤（递归公式），很容翻译成代码的。
我们再回忆一下归分算法的步骤：
轻松翻译成代码：
function quickSort(array) {  let pivot = array[array.length - 1]  let left = array.filter((v, i) => v <= pivot && i != array.length -1)  let right = array.filter(v => v > pivot)  return [...quickSort(left), pivot, ...quickSort(right)]}[color=rgba(140, 140, 140, 0.8)]复制代码
递归是自身调用自身，不能无限次的调用下去，因此需要有递归出口（初始条件）。
它的递归出口是，当数组元素个数为小于2时，就是已经是排好序的，不需要再递归调用了。
因此需要在前面加入代码：
if (array.length < 2) return array

作者: 晨大喵    时间: 2020-5-14 17:12
你好棒啊  加油~
作者: xiaowang66    时间: 2020-5-14 18:22
加油



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2