概述
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(nlogn)次比较。事实上，快速排序通常明显比其他Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来，并且在大部分真实世界的数据，可以决定设计的选择，减少所需时间的二次方项之可能性。
快速排序，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序,以达到整个序列有序的目的。
形象图示：
步骤
选择一个基准元素，通常选择第一个元素或者最后一个元素
通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值均比基准值大
此时基准元素在其排好序后的正确位置
然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。
实例
原始数据：
3 5 2 6 2
选择 3 作为基准
第一轮
|
1
2
3
4
5
6
7
|
从右往左找比3小的，2符合，将2和3对调2 5 2 6 3对调一次，查找的方向反向，从左向右找比3大的，5符合，对调2 3 2 6 5再从右往左找比3小的，2符合，对调2 2 3 6 5一轮结束 |
第二轮
|
1
2
|
对 [2 2] 采用同上的方式进行，得到2 2 3 6 5 |
第三轮
|
1
2
|
对 [6 5] 采用同上的方式进行，得到2 2 3 5 6 |
最终结果
2 2 3 5 6
代码实现(Java)
|
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
package com.coder4j.main.arithmetic.sorting;public class Quick { private static int mark = 0; /** * 辅助交换方法 * * @param array * @param a * @param b */ private static void swap(int[] array, int a, int b) { if (a != b) { int temp = array[a]; array[a] = array[b]; array[b] = temp; // 找到符合的，对调 System.out.println("对调" + array[a] + "与" + array[b] + ",得到"); for (int i : array) { System.out.print(i + " "); } System.out.println(); } } /** * 新一轮分隔 * * @param array * @param low * @param high * @return */ private static int partition(int array[], int low, int high) { int base = array[low]; mark++; System.out.println("正在进行第" + mark + "轮分隔，区域：" + low + "-" + high); while (low < high) { while (low < high && array[high] >= base) { high--; System.out.println("从右往左找比" + base + "小的，指针变动：" + low + "-" + high); } swap(array, low, high); while (low < high && array[low] <= base) { low++; System.out.println("从左往右找比" + base + "大的，指针变动：" + low + "-" + high); } swap(array, low, high); } return low; } /** * 对数组进行快速排序，递归调用 * * @param array * @param low * @param heigh * @return */ private static int[] quickSort(int[] array, int low, int heigh) { if (low < heigh) { int division = partition(array, low, heigh); quickSort(array, low, division - 1); quickSort(array, division + 1, heigh); } return array; } /** * 快排序 * * @param array * @return */ public static int[] sort(int[] array) { return quickSort(array, 0, array.length - 1); } public static void main(String[] args) { int[] array = { 3, 5, 2, 6, 2 }; int[] sorted = sort(array); System.out.println("最终结果"); for (int i : sorted) { System.out.print(i + " "); } }} |
测试输出结果：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
全选复制放进笔记正在进行第1轮分隔，区域：0-4对调2与3,得到2 5 2 6 3 从左往右找比3大的，指针变动：1-4对调3与5,得到2 3 2 6 5 从右往左找比3小的，指针变动：1-3从右往左找比3小的，指针变动：1-2对调2与3,得到2 2 3 6 5 从左往右找比3大的，指针变动：2-2正在进行第2轮分隔，区域：0-1从右往左找比2小的，指针变动：0-0正在进行第3轮分隔，区域：3-4对调5与6,得到2 2 3 5 6 从左往右找比6大的，指针变动：4-4最终结果2 2 3 5 6 |
经测试，与实例中结果一致。
