数据结构与算法——快速排序

快速排序，顾名思义，它速度很快，针对一般应用中各种不同的输入都要比其他排序算法快很多，因此在各种排序算法中，应用最广泛。

快速排序将数组排序的方式是 ：先取数组中第一个元素作为切分元素，同时正向、反向遍历数组，通过若干次交换元素，将处于数组第一个位置的切分元素交换到合适的位置，使得切分元素左边的元素全小于等于它，切分元素右边的元素全部大于等于它。此时切分元素已排定了，如果再将切分元素左边的子数组和右边子数组都排序，那么由切分元素左数组、切分元素、切分元素的右子数组组成的数组就是有序的。

示意图如下，K是切分元素，放到合适位置后，分别将切分元素左右子数组都进行排序，之后数组变得有序。

左右数组的排序是通过递归调用切分来排序的。由归纳法不难证明递归能够正确地将数组排序：如果左子数组和右子数组都是有序的，那么左子数组、切分元素、右子数组三者组成的结果数组也一定有序。所以通过递归不断将数组从切分元素处（得先求得切分元素）分解成左右两半，每次递归调用都会排定一个元素——就是切分元素，且保持着切分元素左边的元素都小于等于它，切分元素右边的元素都大于等于它这个关系。随着递归的深入，数组被分解得很小，它们依然满足前述关系，最后当数组被分解到最小时（即只有一个元素），已经不能再切分，依然很好地维持着这个关系。

可以看到，快速排序的关键在于切分，整个算法自始至终满足下面三个条件：

• 对于某个切分元素a[j]，它已经排定；
• a[low]到a[j - 1]中所有元素都小于等于a[j];
• a[j + 1]到a[high]中的所有元素都大于等于a[j].

切分的一般做法是：随意取a[low]作为切分元素，先从数组的左端开始向右扫描直到找到第一个大于等于切分元素的元素，然后从数组的右端开始向左扫描直到找到第一个小于等于切分元素的元素。这两个元素对于切分元素，位置顺序显然是不对的，因此交换它们使得数组满足上面的条件2、条件3；接着扫描、交换元素，直到从左到右的指针i大于等于从右到左的指针j（表示两个扫描指针相遇），此时只需将a[low]和a[j]交换位置，切分元素就被放到了合适的位置。最后返回j表示切分元素的位置，给下次递归排序调用。

下图说明了切分前后的示意图。

由上面的描述已经可以写出切分的代码了

public class QuickSort {

    private static int partition(Comparable[] a, int low, int high) {
        // 下面使用++i和--j的形式，因此i和j的定义如下
        int i = low;
        int j = high + 1;
        // 切分元素保存下来
        Comparable v = a[low];

        while (true) {
            // 从左到右扫描，直到遇到大于等于v的元素为止
            while (less(a[++i], v)) {
                if (i == high) {
                    break;
                }
            }
            // 从右到左扫描，直到遇到小于等于v的元素为止
            while (less(v, a[--j])) {
                if (j == low) {
                    break;
                }
            }
            // 由于指针是先自增，所以先判断指针是否相遇，相遇就退出while
            if (i >= j) {
                break;
            }
            // 若没有相遇就交换元素
            swap(a, i, j);
        }
        // 切分元素交换到合适的位置
        swap(a, low, j);
        return j;
    }
}

最后为什么是low和j交换（而不是和i），切分元素就换到了合适的位置？

看图说明一切

最后一次交换i = 5, j = 6，while循环继续，所以i变成6，j变成5，break跳出。将i处的L与切分元素K交换肯定是不对的（这样比K大的L排在了切分元素的左边），所以应该用位置j处的E和切分元素交换，结果如上头最后一行所示，是正确的。

接着写快速排序的代码就顺理成章了。

public static void sort(Comparable[] a) {
    // 随机打乱数组，大大减小最坏情况的概率
    shuffle(a);
    sort(a, 0, a.length - 1);
}

private static void shuffle(Comparable[] a) {
    // asList返回的是实际上是ArrayList，而ArrayList的底层是数组，所以打乱了b，a也被打乱了
    List<Comparable> b = Arrays.asList(a);
    Collections.shuffle(b);
}

private static void sort(Comparable[] a, int low, int high) {
    // 当只有一个元素时，不能再切分，直接返回
    if (high <= low) {
        return;
    }
    // 切分元素已经排定
    int j = partition(a, low, high);
    // 对切分元素左数组排序
    sort(a, low, j - 1);
    // 对切分元素右数组排序
    sort(a, j + 1, high);
    // 三者结合起来的数组有序！
}

注意在排序之前，对数组进行了随机打乱。这个操作是有必要的！虽然看似多了一两步操作，但试想一种极端的情况：如果切分元素本来就是数组中最小或者最大的，每次调用只会有一个元素被交换，剩下的数组还是一个大数组；如果第二次切分元素依然是最小或者最大的元素....这将导致一个大子数组需要切分很多次，我们事先打乱数组就是为了规避这种情况。它能使产生糟糕的切分情况的可能性降到极低。

对一个数组的快速排序轨迹，见下图

红色圆圈的元素就是被换到合适位置后的切分元素。

快速排序的效率依赖于切分数组的效果，而这依赖于切分元素的值，切分有可能发生在数组中的任何位置。如果每次切分都发生在数组的中间，即每次都能将数组对半分，这是最好情况。

快速排序的时间复杂度为O(Nlg N)

快速排序的改进

对于任何递归的排序算法，当数组规模较小时，切换到插入排序是个明智的选择。因为

• 对于小数组，快速排序比插入排序慢；
• 因为递归，快速排序的sort方法在小数组中也会调用自己。

private static void sort(Comparable[] a, int low, int high) {
    // high = low说明数组被划分到只有一个元素，不能再切分，直接返回
    // high <= low + 15 说明当数组长度不超过16时都换用插入排序

    if (high <= low + 15) {
        InsertSort.sort(a);
        return;
    }
    // 切分元素已经排定
    int j = partition(a, low, high);
    // 对切分元素左数组排序
    sort(a, low, j - 1);
    // 对切分元素右数组排序
    sort(a, j + 1, high);
    // 三者结合起来的数组有序！
}

三向切分的快速排序

实际应用中可能出现大量重复元素，最特殊的情况：一个数组中所有元素都相同，此时无需继续排序了，但是上述算法还是会对数组进行切分。基于此可以将数组切分成三部分，分别对应小于、等于、大于切分元素的数组元素。

我们来看这种被称为三向切分的快速排序。它从左到右遍历数组一次，维护一个指针lt使得a[low...lt-1]中的元素都小于v，一个指针gt使得a[gt + 1...high]中的元素都大于v，一个指针i使得a[lt..i-1]中的元素都等于v，a[i..gt]中的元素暂定。一开始i和low相等。随着循环，a[i...gt]越来越小，即gt-i不断减小，当i > gt时循环结束。循环中进行下面的操作：

• 如果a[i]小于v，将a[i]和a[lt]交换，lt和i都加1；
• 如果a[i]大于v，将a[i]和a[gt]交换，gt减1；
• 如果a[i]等于v，将i加1

上面的这些操作保证了最后i > gt可以推出循环。

三向切分的快速排序示意图如下：

代码如下

public class Quick3way {

    public static void sort(Comparable[] a) {
        shuffle(a);
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int low, int high) {
        if (high <= low) {
            return;
        }

        int lt = low;
        int gt = high;
        int i = low + 1;
        // 切分元素
        Comparable v = a[low];
        while (i <= gt) {
            int cmp = a[i].compareTo(v);
            if (cmp < 0) {
                swap(a, lt++, i++);
            } else if (cmp > 0) {
                swap(a, i, gt--);
            } else {
                i++;
            }
        }
        // 现在a[lo..lt-1] < v=a[lt..gt] < a[gt+1..high]成立
        // 切分元素相同的数组不会被递归算法访问到，对其左右的子数组递归排序
        sort(a, low, lt - 1);
        sort(a, gt + 1, high);
    }
}

这段排序能够将和切分元素相等的元素聚集到一块儿，这样它们就不会被包含在递归调用处理的子数组中了。对于存在大量重复元素的数组，这种方法比标准的快速排序要快。三向切分的最坏情况是所有元素各不相同，这时会比标准的快速排序要慢，因为比起标准的快速排序使用了更多的比较。

结合上图来看，上面代码做的事情是：

• 在指针i的移动过程中，如果a[i]比切分元素v小，就将a[i]交换到左边（具体做法是将a[i]于a[lt]交换，同时lt和i都要向右移动一格，相当于新元素插入进来了嘛，要腾出空间的）从而保证了a[low..lt-1]中的元素都比v小；
• 如果a[i]比v大，将a[i]交换到右边，具体做法是将a[i]和a[gt]交换，此时只需将gt向左移动一格，lt和i都无需移动（看图可以很好理解），从而保证了a[gt+1..high]中的元素都比v要大；
• 如果a[i]和v相等，只需将i向右移动一格，相当于将a[i]添加到相等切分元素集合的末尾，从而保证了a[lt...i-1]中的元素都等于v。

由于i和gt不能同时改变，最后退出循环时，必然有关系i = gt +1，所以最后a[lt...i-1] = a[lt...gt]中的元素都和v相等。这串元素都不会被包含在递归调用的排序中，排除掉它们后，在递归调用中自然是sort(a, low, lt - 1); sort(a, gt + 1, high);了。

三向切分的快速排序轨迹如下图所示。

对于包含大量重复元素的数组，三向切分的快速排序算法将排序时间从线性对数级降低到线性级别，因此时间复杂度介于O(N)和O(Nlg N)之间，这依赖于输入数组中重复元素的数量。

快速排序交换两个元素跨度很大，是跳跃性的，可以想象这很容易造成等值元素相对位置改变。而且从代码中可以更直观的看出，左往右扫描时，是遇到大于等于切分元素停止，右往左扫描时是遇到小于等于切分元素停止，如果都是遇到等于切分元素时停止，切分中将会交换这两个相等的元素，因此等值元素的相对位置改变，即快速排序不是稳定的排序算法。

by @sunhaiyu

2017.10.30