JavaScript如何快速排序
基本思想
1 在数据集之中，选择一个元素作为"基准"（pivot）。 2 所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。 3 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
举个栗子
let array = [2, 9, 6, 3, 80, 34, 7, 8];
JavaScript如何快速排序
function quickSort(list) {
if(list.length <= 1) { return list; }
let left = [], right = [];
let pivotIndex = Math.floor(list.length / 2);
let pivot = list.splice(pivotIndex, 1)[0];
for(let index = 0, len = list.length; index < len; index++) {
let val = list[index];
if(val <= pivot) {
left.push(val);
} else {
right.push(val);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}输出： [2, 3, 6, 7, 8, 9, 34, 80]
quickSort函数解构
let left = [], right = [];
let pivotIndex = Math.floor(list.length / 2);
let pivot = list.splice(pivotIndex, 1)[0];
for(let index = 0, len = list.length; index < len; index++) {
let val = list[index];
if(val <= pivot) {
left.push(val);
} else {
right.push(val);
}
}这部分逻辑正是对基本思想中的1、2点的实践。
- #### 1 找出基准数
let pivotIndex = Math.floor(list.length / 2);
let pivot = list.splice(pivotIndex, 1)[0];- #### 2 以“基准”二分数组
for(let index = 0, len = list.length; index < len; index++) {
let val = list[index];
if(val <= pivot) {
left.push(val);
} else {
right.push(val);
}
}- #### 3 重复1、2点
在栗子中的数组执行一次1、2点实现后，你会发现此时执行后出现三个结果 1）letf = [2]; 2）pivot = 3; 3）right = [9, 6, 80, 34, 7, 8];
然后依次组合
[...left, pivot, ...right]
// [2, 3, 9, 6, 80, 34, 7, 8]你会发现left只有一个元素，那就没有必要继续对left排序，所以没有必要再排序
if(list.length <= 1) { return list; }然后再看right，并不是有序数组。那要怎么办？继续对right排序，调用quickSort
quickSort(right)
// [...quickSort(left), pivot, ...quickSort(right)];而
return [...quickSort(left), pivot, ...quickSort(right)];正是对第3点的实践。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018年10月25日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录