注:图片来源于文章(https://segmentfault.com/a/1190000015316531)
快速排序采用了一种分治的思想,由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用。快速排序是一种不稳定的排序方法。该方法的基本思想是:
- 定基准:先从数列中取出一个数作为基准数;
- 分区:将比这个数打的数全放到它的右边,小于或等于它的数全放到它的左边;
- 再对左右两个区间重复第二步,直到各区间只有一个数(终止条件)。
上面三步中,第一步定基准的方式比较多样化,网上大体有三种方式(具体用哪一种个人觉得没啥差别):
- 找数组中位于中间位置的一个数作为基准(参考文章后面的代码实现);
- 直接选数组中第一个数作为基准;
- 取首尾中三个数的中位数作为基准(参考文章开头的图片)。
递归实现:
function quickSort (arr) { // 数组长度小于2就直接返回,不需要再处理了,这个就是快排的终止条件 if (arr.length <= 1) { return arr } // pivot意思是:枢纽、中心点 var pivotIndex = Math.floor(arr.length / 2) // 找基准,并把基准从原数组中删除 var pivot = arr.splice(pivotIndex, 1)[0] // 定义左右数组 var left = [] var right = [] // 比基准小的放在left,比基准打的放在right arr.forEach(function (val) { if (val <= pivot) { left.push(val) } else { right.push(val) } }) // 递归 return quickSort(left).concat([pivot], quickSort(right)) }