快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。1

算法原理

  1. 从数列中选取一个数作为基准(pivot)
  2. 将数列中比pivot小的数移动到pivot左边，比pivot大的数移动到pivot右边。
  3. 以pivot为界，将数列分成两个子列，这样前一个子列的数都比都一个子列的要小。
  4. 对子列重复1-3的操作，直到所有子列都有序。

步骤分析

我认为在这个算法中，前面提到的第二步是比较困难。这里采用“挖空填空”的思路。

这里的在某位置挖空意思是某数据可以被覆盖，例如一种常见交换变量的方法：

/**
    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右移。

实例代码(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

                    ↑

需要导入

import java.util.Arrays;
import java.util.stream.Stream;

代码如下

    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。

  1. 摘自百度百科 ↩
  2. 这里使用了拟人的手法，事实上：下标寻找 -> 比较；挖空 -> 把下标当成一个标记，记录这个数据下一次将要被覆盖。 ↩
  3. 从java7开始，使用的是quicksoft的改进算法， DualPivotQuicksort，即使用两个pivot将数组分成三块，这种方法在现代计算机上更有优势。PDF ↩
  4. 需要java8。 ↩
最后修改：2020 年 04 月 07 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏