手撸排序:快速排序

核心思想

首先算法理解了主要思想,那么代码实现也是信手拈来

快排分以下三步:

  • 找基准:挑一个基准数用来分割当前数组,我们称该数为”基准”(pivot)
  • 分割:把数组里小于”基准”的数放到左边,遍历一遍操作后数组就分割好了,最麻烦的也是这步分割操作了
  • 递归:对分割后的数组重复第一二步,直到最后数组长度为1或0,就代表已经排好可以返回了

实例分析

首先我们用lodash创建一个随机数组

1
2
_.shuffle([1,2,3,4,5,6,7,8,9,10])
// [2, 3, 4, 1, 7, 5, 8, 10, 9, 6 ]

现在将它进行排序

首先选取基准数,我们就直接取最后一位作为基准数,左起设一个index值记录替换次数,每替换一次index自增1

然后从左至右开始遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
[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]
// 然后再分别将这两个数组进行重复上述操作

有了上述思路就可以开始撸代码了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 定义交换逻辑
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
}

代码可能较其他方法冗余,个人认为这是思路最清晰的写法

测试

然后加一些测试代码

1
2
3
4
5
6
7
8
9
10
11
12
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