Loading... 快速排序(Quicksort)是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。[^1] [^1]: 摘自[百度百科](https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/369842) ### 算法原理 1. 从数列中选取一个数作为基准(pivot) 2. 将数列中比pivot小的数移动到pivot左边,比pivot大的数移动到pivot右边。 3. 以pivot为界,将数列分成两个子列,这样前一个子列的数都比都一个子列的要小。 4. 对子列重复1-3的操作,直到所有子列都有序。 ### 步骤分析 我认为在这个算法中,前面提到的第二步是比较困难。这里采用“挖空填空”的思路。 这里的在某位置挖空意思是某数据可以被覆盖,例如一种常见交换变量的方法: ```java /** array.length() = 2, 求array的倒序. */ public void swap(Object[] array) { Object tmp = array[0]; // 在array[0]位置挖空 array[0] = array[1]; array[1] = tmp; } ``` 为了方便起见,我们选取数列最左端的数作为pivot,将待排列的数组记作array,同时定义两个int left,和int right记录数组下标。 首先因为我们选取了最左端的数作为pivot,就相当于在array[0]挖了一个空,所以我们先比较array[right]。 - 若array[right]比pivot大(或等于),则说明array[right]位置正确,right下标向左移动一位,重复比较操作。 - 若array[right]比pivot小,则说明array[right]应该在pivot的左边,之前我们已经在array[0]处挖了个空,所以我们将array[0]设置为array[right]。这时候我们在array[right]处挖了个空,结束第一次移动。 将left下标向右移动一位,比较array[left],下面的操作和上面的很相似。 - 若array[left]比pivot小(或等于),则说明array[left]位置正确,left下标向右移动一位,重复比较操作。 - 若array[left]比pivot大,则说明array[left]应该在pivot的右边,由于之前我们已经在array[right]处挖了个空,所以我们将array[right]设置为array[left]。这时候我们在array[left]处挖了个空,结束第二次移动。 经过上面两个操作交替进行若干次,最终left=right,第一次排序结束,我们得到了两个子列array[i]\(i=0,1,2···,left - 1),和array[I]\(i=right + 1, right + 2,······,n),对得到子列重复上述操作,直到子列长度为1,这样我们就完成了数组的排序。 ### 示意图 下面我用图形表示一下这个过程,两个箭头表示下标的位置,括号表示挖空的数据。 - 0x01 __选取&比较__ 选取4作为pivot 比较right和pivot $$ \begin{matrix} ↓&&&&&&&\\ (4)&7&6&2&1&8&2&\\ &&&&&&↑&\\ \end{matrix} $$ - 0x02 __赋值__ 4 > 2 -> 将left设置为2 $$ \begin{matrix} ↓\\ 2&7&6&2&1&8&(2)\\ &&&&&&↑ \end{matrix} $$ - 0x03 __移动&比较__ 将left向右移动一位 比较left和pivot $$ \begin{matrix} &↓&&&&&&\\ 2&7&6&2&1&8&(2)&\\ &&&&&&↑&\\ \end{matrix} $$ - 0x04 __赋值__ 4 < 7 -> 将right设置为7 $$ \begin{matrix} &↓&&&&&&\\ 2&(7)&6&2&1&8&7&\\ &&&&&&↑\\ \end{matrix} $$ - 0x05 __移动&比较__ 将right向左移动一位 比较right和pivot $$ \begin{matrix} &↓&&&&&&\\ 2&(7)&6&2&1&8&7&\\ &&&&&↑\\ \end{matrix} $$ - 0x06 __再次移动&比较__ 4 < 8 -> 将right再向左移动一位 比较right和pivot $$ \begin{matrix} &↓&&&&&&\\ 2&(7)&6&2&1&8&7&\\ &&&&↑\\ \end{matrix} $$ - 0x07 __赋值__ 4 > 1 将left设置为1 $$ \begin{matrix} &↓&&&&&&\\ 2&1&6&2&(1)&8&7&\\ &&&&↑\\ \end{matrix} $$ - 0x08 __移动&比较__ 将left向右移动一位 比较left和pivot $$ \begin{matrix} &&↓&&&&&\\ 2&1&6&2&(1)&8&7&\\ &&&&↑\\ \end{matrix} $$ - 0x09 __赋值__ 4 < 6 将right设置为6 $$ \begin{matrix} &&↓&&&&&\\ 2&1&(6)&2&6&8&7&\\ &&&&↑\\ \end{matrix} $$ - 0x0A __移动&比较__ 将right向左移动一位 比较right和pivot $$ \begin{matrix} &&↓&&&&&\\ 2&1&(6)&2&6&8&7&\\ &&&↑\\ \end{matrix} $$ - 0x0B __赋值__ 4 > 2 将left设置为2 $$ \begin{matrix} &&↓&&&&&\\ 2&1&2&(2)&6&8&7&\\ &&&↑\\ \end{matrix} $$ - 0x0C __移动&检测__ 将left向右移动一位 $$ \begin{matrix} &&&↓&&&&\\ 2&1&2&(2)&6&8&7&\\ &&&↑\\ \end{matrix} $$ - 0x0D __赋值__ 将left(right)设置为pivot $$ \begin{matrix} &&&↓&&&&\\ 2&1&2&4&6&8&7&\\ &&&↑\\ \end{matrix} $$ 至此,原数列被分成两个子列Arrays.copyOfRange(array, 0, left -1)和Arrays.copyOfRange(array, right + 1, array.length()),左边的子列中的数都比pivot小,右边的都比pivot大。第一次排序结束。 ### 小结 从上面的示意图分析我们可以知道[^2] - 下标left和right的作用是从两个方向扫描数列,left寻找比pivot大的数,right寻找比pivot小的数。 - 当下标left和right发现“位置错误”的数时,会将这个数赋值给上一次挖空的位置,然后在这次寻找到的位置挖空。 - 下标left挖空后,right左移;下标right挖空后,left右移。 [^2]: 这里使用了拟人的手法,事实上:下标寻找 -> 比较;挖空 -> 把下标当成一个标记,记录这个数据下一次将要被覆盖。 ### 实例代码(Java) 直接按照上面示意图分析,不难写处这个代码。 ```java /** * 使用快速排列算法排序数组. * @param array 待排序的数组 * @param start 数组起始下标 * @param end 数组结束下标 */ public static void quickSort(int[] array, int start, int end) { if (end - start + 1 <= 1) { // 数组长度小于等于1 return; } int pivot = array[start]; // 选取最左边的数作为基准 int left = start; // 下标 left int right = end; // 下标 right sort:while(true) { while(true) { if (left == right) { break sort; } if (array[right] < pivot) { // 下标right的数小于pivot array[left] = array[right]; left++; break; } else { right--; } } while(true) { if (left == right) { break sort; } if (array[left] > pivot) { // 下标left的数大于pivot array[right] = array[left]; right--; break; } else { left++; } } } array[left] = pivot; quickSort(array, start, left -1); // 递归排序左子列 quickSort(array, right + 1, end); // 递归排序右子列 } ``` 当然这段代码右很多地方可以优化,例如可以将比较语句放到循环条件处,将赋值语句提到循环结构外。 另外这个提供一个调试用的代码,在每次执行操作前调用,可以输出这样的信息: > count=1, pivot=4, start=0, end=6 > ↓ > 4 7 6 2 1 8 2 > ↑ 需要导入 ```java import java.util.Arrays; import java.util.stream.Stream; ``` 代码如下 ```java static int count = 0; public static void debug(int[] array, int start, int end, int left, int right, int pivot) { count++; System.out.println("\n\ncount=" + count + ", pivot=" + pivot + ", start=" + start + ", end=" + end); StringBuilder[] strs = Stream.generate(StringBuilder::new).limit(3).toArray(StringBuilder[]::new); for(int i=0;i<array.length;i++) { if (i == left) { strs[0].append("↓\t"); } else { strs[0].append("\t"); } if (i == right) { strs[2].append("↑\t"); } else { strs[2].append("\t"); } strs[1].append(array[i]).append("\t"); } Arrays.stream(strs).forEach(System.out::println); } ``` ### 后记 这里给出的快速排序代码是比较粗糙的,实际使用过程中还有很多的地方可以优化,比如取数组中间的数作为pivot,优化控制代码,根据数组的大小调整排序的方案等,有兴趣可以参考java.util.Arrays#sort(int[])[^3],另外快速排序是一个分治算法,可以方便地进行并行处理,可参考java.util.Arrays#parallelSort(int[])[^4]。 [^3]: 从java7开始,使用的是quicksoft的改进算法, DualPivotQuicksort,即使用两个pivot将数组分成三块,这种方法在现代计算机上更有优势。[PDF](https://arxiv.org/pdf/1511.01138.pdf) [^4]: 需要java8。 最后修改:2020 年 04 月 07 日 © 允许规范转载 赞 0 如果觉得我的文章对你有用,请随意赞赏