阮一峰快速排序
本打算学一波快速排序，查了查资料，吓一大跳，说阮一峰大神的快排是不对的，以此开始了一大波大神针对这个问题的各种观点。感兴趣的可以看看知乎这篇帖子：
https://www.zhihu.com/question/276746146/answer/390729075
不管对还是错，阮一峰大神的快排思路是对的：
在数据集之中，选择一个元素作为"基准"（pivot）。
所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
先看看阮一峰大神的代码：
var quickSort = function(arr) {
if (arr.length <= 1) {return arr; }//判断数组，一个长度直接返回
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];//找出基准元素
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
//循环把元素分别放入左边和右边数组
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};思路很清晰找出基准之后，左边数组右边数组和基准的数组都很清晰。
那些说为什么用splice（splice本身也有时间复杂度）、为什么每次开辟新的left、right数组等，这确实是这段代码的问题。但是阮一峰大神只是提供思路，这些问题都是能优化的。当时ES6也没出来，以后还会有更多的数组扩展，那不是能更简单的实现快速排序，但是快速排序的思路是不变的。
我本来想把两个都优化了，奈何能力有限，无法解决一直开辟新数组的问题，也就是空间复杂度的问题：
var quickSort = function(arr) {
if (arr.length <= 1) { return arr; }
var pivot = arr[0];
var left = [];
var right = [];
var mid = [];
for (var i = 0; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else if (arr[i] > pivot){
right.push(arr[i]);
}else{
mid.push(arr[i]);
}
}
return quickSort(left).concat(mid, quickSort(right));
};如果有大神知道，希望能告知优化方法。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-04-11，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读