你真的完全理解了快速排序吗？如果没有请仔细阅读本文，让我们一起成长。废话不哆嗦，开始今天的学习——快速排序，单独说明快速排序是因为其重要，首先快速排序是基础排序算法中表现比较亮眼的，其次是因为快排还有很多的改进方式，具体介绍如下。



快速排序基础



快速排序的思想是采用分治的算法思想，具体算法是选择一个随机元素，通常是待排数组的起点，然后设置前后指针，对比确定该元素的位置，并且在确定位置的过程中进行数据交换，让确定元素位置的之前的元素都小于选择的元素，让后面的元素都大于该元素，那么这个元素的位置在整个数组中就是确定；然后以此类推，在数组前半部分循环上面步骤，在数组后半部分循环使其有序，直到分到一个元素时，即得到一个序列有序。具体代码如下：

public static void sort(int[] nums, int low, int high){
    Array.nonEmpty(nums);
    if(low < high){
        int mid = partition(nums, low, high);
        sort(nums, low, mid-1);
        sort(nums, mid+1, high);
    }
}
public static int partition(int[] nums, int low, int high){
    int temp = nums[low];
    while(low < high){
        while (low < high && nums[high] >= temp) high--;
        	nums[low] = nums[high];
        while (low < high && nums[low] < temp) low++;
        	nums[high] = nums[low];
    }
    nums[low] = temp;
    return low;
}

快速排序是不稳定的排序，不稳定的原因就是元素的跨节点的交换，如果是相邻交换，则是稳定排序，快速排序的平均时间复杂度为O(nlgn)，最坏时间复杂度为O(n^2)，但由于其出现最坏的情况较少，所以其排序性能在排序算法中算好的。



改进一



考虑一下这种情况，数组有序，然后应用快速排序对数组排序，按照上面的实现，选择最小的元素为随机元素，那么这时的快排就变成了O(n^2)，所以改进思路就是让随机元素变“随机”，改进的第一种思路产生了。下面只给出修改的代码：

public static int partition(int[] nums, int low, int high){
    // 让随机元素变的随机
    swap(arr[low], arr[rand() % (high - low + 1) + low]);
    int temp = nums[low];
    while(low < high){
        while (low < high && nums[high] >= temp) high--;
        	nums[low] = nums[high];
        while (low < high && nums[low] < temp) low++;
        	nums[high] = nums[low];
    }
    nums[low] = temp;
    return low;
}

这种改进方式对已经有序的数组是有效的，能够降低其时间复杂度。



改进二



试想这样一种情况，排序数组中存在大量的重复元素，那么在分治的过程中，相同元素会分布在同一个分区中，如果重复元素比较多，会造成分区的长度极不平衡，增加排序的复杂度。基于此我们可以提出两种改进方式，其中一种是将重复的元素均匀的分部在两个分区中，这样解决了大于、小于两个分区长度不平衡的问题，这种改进方式为双路快排，代码实现如下：

private static int partition(int[] nums, int start, int end) {  // 排序方法和普通快排相同
    int i = start + 1;
    int j = end;
    int v = nums[start];
    while (true) {
        while (i <= end && nums[i] < v) i++;
        while (j >= start + 1 && nums[j] > v) j++; // 没有等号，否则从这就直接走了
        if (i > j) break;
        swap(nums, i, j);
        i++;
        j--;
    }
    swap(nums, start, j);
    return j;
}

大量重复元素进行排序时，普通快排由于递归层数较大，很快就是栈溢出，但是在百万级重复元素的情况下，双路快排还是能够快速将数据排好，很强悍！但是，这种方式虽然让分区平衡，但是其没有解决相同元素比较的问题，所以这就是产生了下一种优化的方式，three-way QS（三路快排），其改进思想是，在原来大于、小于两个分区的基础上增加一个等于的分区，将原来的两个分区，扩充至三个分区，这样等于的分区中元素就可以不参与排序，而直接排好大于和小于两个分区的元素即可，具体代码实现如下：

private static void sort(int[] array, int start, int end) {
    Arrays.nonEmpty(array);    
    if (start > end) return;
    //找到一个随机key
    int value = array[start];
    int lt = start; int gt = end + 1; int i = start + 1;
    while (i < gt) {
        if (array[i] < value) {
            swap(array, i, lt + 1);
            lt++; i++;
        } else if (array[i] > value) {
            swap(array, i, gt - 1);
            gt--;
        } else i++;
    }
    swap(array, lt, start);
    //直接跳过相等元素的比较
    sort(array, start, lt - 1);
    sort(array, gt, end);

三路快排很好的解决了数据重复的问题，能够在数据大量重复的情况下，提升排序性能（这里就不给出性能对比了）；



改进三



在快排算法中还有一种改进方式，即内省式快排，在STL中的快排使用的就是这种算法。首先看一下这种改进方式针对的问题以及改进的思路。



1.为什么需要这种算法



快排在排序小数组（比如大小为10的数组）且基本有序的情况下，它的表现还没插入排序要好（很多改进是在分区起止位置小于一定长度后改用插入排序）。因为数组是基本有序，使得插入排序不用很多次的执行元素的移动，并且可以避免递归。 在SGI STL中的函数sort使用的排序算法就是内省式的排序算法。内省的排序算法是基于快排实现的。假设待排序的数组大小为n，去一个k值，使得k为满足2^k <= n的最大值。k为最大的递归层次、 为什么要设置最大递归层次呢？ 因为快排的递归层次过深的时候，很可能会退化成O(n^2)。内省式排序使用k来控制快排的递归深度，当快排的递归深度到达k的时候选择使用heap排序。



2. 为什么不一开始就使用heap排序



heap排序在平均时间复杂度是O(nlgn)，最坏情况也是O(nlgn)，看起来要比快排要快。但是实际上，快排是要比heap排序要快，第一个原因是：heap排序虽然和快排在平均情况下的时间复杂度是O(nlgn)，但是heap排序的时间常数要比快排的时间常数要大。第二个原因是：据统计，快排的最坏情况在是很少发生的。第三个原因是：快排能够比较好的吻合程序的空间局部性原理，因为它操作的基本都是相邻的元素（虚拟存储器的设计理论基础中就有程序的时间局部性和空间局部性），能够减少内存缺页中断的发生次数。



3.为什么要使用heap排序呢



因为在递归层次太深的时候，就意味着发生最坏情况的概率大大的提升了，这时候因为heap排序的最坏情况下的时间复杂度是O(nlgn)比快排的O(n^2)要好，因此使用heap排序能更好优化排序效率。



基于以上三点，诞生了一种新的改机算法，即内省排序，名字很符合算法思想，自我省查，发现苗头不对，立即采用候补排序算法，不是一条道走到黑，算法领域的思想和人生是多么相似，只有这样才能获得很好的性能表现；这个算法就不给出具体实现了，主要是有点复杂，但是这种改进算法的思路值得我们思考借鉴，



总结



本文主要是介绍了快速排序及其几种改进思路，要改进一种算法必须是建立在对其十分了解并且充分思考过后的，学习算法思想是一方面，但对于大多数人来说，算法高效实现才是比较考验人的，好多人都是知道其思想，但是实现不了，读万卷书，还要行万里路，在编程领域，后者更为重要，完毕。



纸上得来终觉浅，绝知此事要躬行。 ——陆游