A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 绮罗 中级黑马   /  2020-5-13 17:28  /  2178 人查看  /  2 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

手写算法并记住它:快速排序(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)]复制代码
至于递归,虽然它不符合线性思维,但其实也没啥难的。
只要有递归步骤(递归公式),很容翻译成代码的。
我们再回忆一下归分算法的步骤:
  • 数组分成三部分left、pivot、right,使left<=pivot,right>pivot
  • 递归处理left
  • 递归处理right
  • 合并三者结果
轻松翻译成代码:
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

2 个回复

倒序浏览
你好棒啊  加油~
回复 使用道具 举报
加油
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马