0%

排序算法

快速排序算法

原理

采用分而治之的思想,每次递归,pivot记住左边都比它小,右边都比它大。

举个例子:

数组 A[p...r]:

  1. 分解:A[p..q-1] A[q+1..r],使得 A[p...q-1]<A[q]<A[q+1..r]
  2. **解决:**递归调用快排,对子数组A[p..q-1]A[q+1..r]排序;
  3. 合并:子问题相互独立的,因此用分治算法就可以了。

具体步骤:

  1. 选择一个元素作为基准pivot(通常取分区的第一个或者最后一个);
  2. 执行重排数列,使得比pivot小的排左边,比pivot大的排右边,这个过程中pivot这个元素所在的坑会不断地被与它对比的元素置换,看起来就像是挖坑填数;
  3. 递归的,使用相同的方式,重排左右两边的子序列。

对比扫描过程分2种:

  • **挖坑排序:**2头向中间扫描,先从后向前找,再从前向后找。
  • 单向扫描

挖坑排序

排序执行流程

以下是首轮比较的过程,2头向中间扫描,先从后向前找,再从前向后找。:

[23] 04 06 08 43 12 78 13 21
21 04 06 08 43 12 78 13 [23]
21 04 06 08 43 12 78 13 [23]
21 04 06 08 43 12 78 13 [23]
21 04 06 08 43 12 78 13 [23]
21 04 06 08 43 12 78 13 [23]
21 04 06 08 [23] 12 78 13 43
21 04 06 08 [23] 12 78 13 43
21 04 06 08 13 12 78 [23] 43
21 04 06 08 13 12 78 [23] 43
21 04 06 08 13 12 78 [23] 43
21 04 06 08 13 12 [23] 78 43

[21 04 06 08 13 12] 23 [78 43]

可以发现[23]这个坑一直在被替换填充。

网上给了很多算法的动态图来展示算法的执行执行流程,不过或许根据现有的数据,自己在脑海中发挥你的想象力让数字动起来也挺有趣的。

爱因斯坦对想象力极为推崇,他曾说过:想象力比知识更重要,因为知识是有限的,而想象力概括着世界上的一切并推动着进步。

激发你的想象力会有更好的记忆效果哦。(嗯,不上动图的借口很有说服力)

实现代码

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public class QuickSort extends Sort {

@Override
public void sort(int[] array) {
quickSort(array, 0, array.length - 1);
}

/**
* 快速排序算法
* @param array 待排序数组区间
* @param left 数组区间开始元素
* @param right 数组区间结束元素
*/
private void quickSort(int[] array, int left, int right) {
// 防守,避免死循环
if (left < right) {
// 根据基准进行排序, 使得比pivot小的排左边,比pivot大的排右边,
// pivotIndex 为基准元素最终的数组下标
int pivotIndex = partition(array, left, right);
// 递归调用两边
quickSort(array, left, pivotIndex - 1);
quickSort(array, pivotIndex + 1, right);
}
}

/**
* 分区, 以选择的基准元素pivot将数组划分为比基准元素大的和比基准元素小的两个分区。
* @param array
* @param start
* @param end
* @return
*/
private int partition(int[] array, int start, int end) {
int seekStart = start;
int seekEnd = end;
int holeValue = array[seekStart];
while (seekStart < seekEnd) {
// 从后向前扫描对比替换前边的坑
while (seekStart < seekEnd && array[seekEnd] >= holeValue) {
seekEnd --;
}
// 找到之后, array[seekEnd]为新的坑
if (seekStart < seekEnd) {
array[seekStart] = array[seekEnd];
// 前边的坑被填掉了,下标加1
seekStart++;
}
// 从前向后扫描对比替换后边的坑
while (seekStart < seekEnd && array[seekStart] <= holeValue) {
seekStart ++;
}
// 找到之后, array[seekStart]为新的坑
if (seekStart < seekEnd) {
array[seekEnd] = array[seekStart];
// 后边的坑被填掉了,下标减1
seekEnd --;
}
}
// 排序完成, 把原来的坑值赋值给最新的那个坑
array[seekStart] = holeValue;
return seekStart;
}

}

单向扫描

排序执行流程

以下是首轮比较的过程,单向从前向后找,找到小的元素则往基准元素前面插队:

[23] 04 06 08 43 12 78 13 21
04 [23] 06 08 43 12 78 13 21
04 [23] 06 08 43 12 78 13 21
04 06 [23] 08 43 12 78 13 21
04 06 [23] 08 43 12 78 13 21
04 06 08 [23] 43 12 78 13 21
04 06 08 [23] 43 12 78 13 21
04 06 08 [23] 43 12 78 13 21
04 06 08 12 [23] 43 78 13 21
04 06 08 12 [23] 43 78 13 21
04 06 08 12 [23] 43 78 13 21
04 06 08 12 13 [23] 43 78 21
04 06 08 12 13 [23] 43 78 21
04 06 08 12 13 21 [23] 43 78

可以发现[23]这个坑一直在被替换填充。

关键是找出基准元素后边比基准元素小的元素后,把该元素往基准元素前面插入,然后基准元素到该元素之间的所有元素往后移动一格。

实现代码

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
* 快速排序算法
*
* Created by arthinking on 9/3/2019.
*/
public class QuickSort extends Sort {

@Override
public void sort(int[] array) {
quickSort(array, 0, array.length - 1);
}

/**
* 快速排序算法
* @param array 待排序数组区间
* @param left 数组区间开始元素
* @param right 数组区间结束元素
*/
private void quickSort(int[] array, int left, int right) {
// 防守,避免死循环
if (left < right) {
// 根据基准进行排序, 使得比pivot小的排左边,比pivot大的排右边,
// pivotIndex 为基准元素最终的数组下标
int pivotIndex = partition(array, left, right);
// 递归调用两边
quickSort(array, left, pivotIndex - 1);
quickSort(array, pivotIndex + 1, right);
}
}

/**
* 分区, 以选择的基准元素pivot将数组划分为比基准元素大的和比基准元素小的两个分区。
* @param array
* @param start
* @param end
* @return
*/
private int partition(int[] array, int start, int end) {
int pivotIndex = start;
int seekEnd = end;
int holeValue = array[pivotIndex];

for (int seekIndex = pivotIndex+1; seekIndex <= seekEnd; seekIndex++) {
// 如果后面的元素小于基准元素, 则往基准元素前面插队
if(array[seekIndex] < array[pivotIndex]) {
array[pivotIndex] = array[seekIndex];
// pivotIndex+1 到 seekIndex(不包括seekIndex)之间的元素往后移动, 在 pivotIndex后面腾出一个位置来放基准元素
for (int temp = seekIndex; temp > pivotIndex + 1; temp --) {
array[temp] = array[temp - 1];
}
// privotIndex 下一个元素处填入基准元素
pivotIndex++;
array[pivotIndex] = holeValue;
}
}
return pivotIndex;
}

}

为了让代码好理解一点,现在我们通过重构手法调整一下partition方法的代码,效果如下:

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
33
34
35
36
37
/**
* 分区, 以选择的基准元素pivot将数组划分为比基准元素大的和比基准元素小的两个分区。
* @param array
* @param start
* @param end
* @return
*/
private int partition(int[] array, int start, int end) {
int pivotIndex = start;
int seekEnd = end;
int holeValue = array[pivotIndex];

for (int seekIndex = pivotIndex+1; seekIndex <= seekEnd; seekIndex++) {
// 如果后面的元素小于基准元素, 则往基准元素前面插队
if(array[seekIndex] < array[pivotIndex]) {
pivotIndex = insertSeekBeforePivot(array, pivotIndex, holeValue, seekIndex);
}
}
return pivotIndex;
}

private int insertSeekBeforePivot(int[] array, int pivotIndex, int holeValue, int seekIndex) {
array[pivotIndex] = array[seekIndex];
// pivotIndex+1 到 seekIndex(不包括seekIndex)之间的元素往后移动, 在 pivotIndex后面腾出一个位置来放基准元素
backwardArray(array, pivotIndex, seekIndex);
// privotIndex 下一个元素处填入基准元素
pivotIndex++;
array[pivotIndex] = holeValue;
return pivotIndex;
}

private void backwardArray(int[] array, int start, int end) {
// 该方法等价于: System.arraycopy(array, start + 1, array, start + 1 + 1, end - (start + 1));
for (int temp = end; temp > start + 1; temp --) {
array[temp] = array[temp - 1];
}
}

练习时间:

ok,了解了算法的实现原理以及实现细节之后,打开开发环境,根据自己脑海中的印象,重新写一遍试试看吧!

温馨提示

理解好了处理流程,那么写伪代码还是比较容易的,但是如果要一次性写对就不那么容易了,特别是临界值比较容易处理错。如果发现不正确,可以在写完代码之后通过debug查看哪一步临界值弄错了,再梳理一下逻辑重新调整代码。

References

Learn-Algorithms

欢迎关注我的其它发布渠道