一些有关快排的小问题

2021-03-06

最近在看《算法（第四版）》，发现了一些有关快排的有趣的小知识。

重复元素

首先请比较这两段代码：

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }
    public void quickSort(int[] nums,int l,int r){
        if(l<r){
            int pivot=nums[l];
            int i=l,j=r;
            while(i<j){
                while(i<j&&nums[j]>=pivot)
                    j--;
                if(i<j)
                    nums[i++]=nums[j];
                while(i<j&&nums[i]<=pivot)
                    i++;
                if(i<j)
                    nums[j++]=nums[i];
            }
            nums[i]=pivot;
            quickSort(nums,l,i-1);
            quickSort(nums,i+1,r);
        }
    }
}

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }
    public void quickSort(int[] nums,int l,int r){
        if(l<r){
            int pivot=nums[l];
            int i=l,j=r;
            while(i<j){
                while(i<j&&nums[j]>pivot)
                    j--;
                if(i<j){
                    nums[i]=nums[j];
                }
                while(i<j&&nums[i]<pivot)
                    i++;
                if(i<j){
                    nums[j]=nums[i];
                }
            }
            nums[i]=pivot;
            quickSort(nums,l,i-1);
            quickSort(nums,i+1,r);
        }
    }
}

第一段是常见的优化填坑法，但是注意第二段，在比较移动时发生了一些微小的变化：当遍历元素等于pivot元素时，不进行移动，而是填坑。

既然相同何必重复填坑？《算法（第四版）》中标注了这个问题的答案：假如在遇到和切分重复的元素时我们继续扫描数组而不是停下来，这种快速排序的方法在处理存在大量重复值数组时时间复杂度会退化为O(n^2)级别。而停下来填坑，尽管会进行一些不必要的操作，但最后pivot值的索引将会更接近中位，时间复杂度近似O(nlogn)。

也有很多面向大量重复元素的快排解法如Dijkstra的”三向切分的快速排序“，在这里不赘述。

为什么要随机

因为快排本身就是偏向随机性的一种排序算法。我们考虑一下最坏情况：当初始数组呈顺序/逆序时，选取首位/末位数字作为pivot进行比较。需要遍历整个数组才能确定一个元素的位置，时间复杂度为O(n^2)。而如果是随机取用元素作为pivot进行比较，会最大程度避免这种糟糕的情况出现。而另一方面，随机取用其实也并不是最佳的算法，最好的选择应该是尽量选取数组的中位数作为pivot，这样才能达到最优复杂度。