沉迷猴姆拉无法自拔
核心思想
首先算法理解了主要思想，那么代码实现也是信手拈来
快排分以下三步：
- 找基准：挑一个基准数用来分割当前数组，我们称该数为"基准"(pivot)
- 分割：把数组里小于"基准"的数放到左边，遍历一遍操作后数组就分割好了，最麻烦的也是这步分割操作了
- 递归：对分割后的数组重复第一二步，直到最后数组长度为1或0，就代表已经排好可以返回了
算法示意图（图源维基百科）
实例分析
首先我们用lodash创建一个随机数组
_.shuffle([1,2,3,4,5,6,7,8,9,10])
// [2, 3, 4, 1, 7, 5, 8, 10, 9, 6 ]
现在将它进行排序
首先选取基准数，我们就直接取最后一位作为基准数，左起设一个index值记录替换次数，每替换一次index自增1
然后从左至右开始遍历
[2, 3, 4, 1, 7, 5, 8, 10, 9, 6 ]
// 6 > 2替换下标为0，0的两个数，index自增1，
[2, 3, 4, 1, 7, 5, 8, 10, 9, 6 ]
// 6 > 3替换下标为1，1的两个数，index自增1
[2, 3, 4, 1, 7, 5, 8, 10, 9, 6 ]
// 6 > 4替换下标为2，2的两个数，index自增1
[2, 3, 4, 1, 7, 5, 8, 10, 9, 6 ]
// 6 > 1替换下标为3，3的两个数，index自增1
[2, 3, 4, 1, 7, 5, 8, 10, 9, 6 ]
// 6 < 7不替换，index为4不变
[2, 3, 4, 1, 7, 5, 8, 10, 9, 6 ]
// 6 > 5替换下标为4, 5的两个数，index自增1
[2, 3, 4, 1, 5, 7, 8, 10, 9, 6 ]
// 6 < 8不替换，index为5不变
[2, 3, 4, 1, 5, 7, 8, 10, 9, 6 ]
// 6 < 10不替换，index为5不变
[2, 3, 4, 1, 5, 7, 8, 10, 9, 6 ]
// 6 < 9不替换，index为5不变
[2, 3, 4, 1, 5, 6, 8, 10, 9, 7 ]
// 遍历结束替换pivot与index下标的值，这样就分割出了两个数组
[2, 3, 4, 1, 5]
[8, 10, 9, 7]
// 然后再分别将这两个数组进行重复上述操作
有了上述思路就可以开始撸代码了
// 定义交换逻辑
function swap(arr, i, j) {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 定义分割逻辑
function partition(arr, left, right) {
const pivot = arr[right];
let index = left;
for (let i = left; i < right; i++) {
if (pivot > arr[i]) {
swap(arr, i, index);
index++;
}
}
swap(arr, right, index);
return index;
}
function sort(arr, left, right) {
if (left > right) return;
const index = partition(arr, left, right);
sort(arr, left, index - 1);
sort(arr, index + 1, right);
}
function quick_sort(arr) {
sort(arr, 0, arr.length - 1);
return arr
}
代码可能较其他方法冗余，个人认为这是思路最清晰的写法
测试
然后加一些测试代码
const _ = require('lodash');
const arr = _.shuffle([1,2,3,4,5,6,7,8,9,10]);
console.log(arr);
console.log(quick_sort(arr));
// [ 8, 3, 9, 4, 7, 1, 6, 2, 5, 10 ]
// [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
// [ 2, 8, 4, 3, 9, 5, 1, 10, 6, 7 ]
// [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
// [ 10, 7, 8, 4, 6, 1, 2, 9, 3, 5 ]
// [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
测试ok
网友评论