前言
原文：[ javascript: 快速排序（Quick Sort） #146 ]
基本思想
1 在数据集之中，选择一个元素作为"基准"（pivot）。
2 所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
3 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
举个栗子
let array = [2, 9, 6, 3, 80, 34, 7, 8];
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)];
}
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点的实践。
