algorithm - 实现随机快速排序算法

Question

CLRS 告诉我们将 A[r] 与 A[i] 交换，其中 i 是 p 和 r 之间的随机变量。但是，如果我随机选择一个变量作为快速排序函数中的基准并交换值，那么现在的时间复杂度是多少？

算法现在的性能会比书中给出的差吗？

这是代码

 package Clrs;
    import java.util.Random;
    public class Clrs
    {
        public static void main(String[] args) 
        {
                int[] a = new int[]{7,6,5,4,3,2,1}; 
                quicksort(a,0,a.length-1);
                        System.out.println(); 

            for (int i : a) {
            System.out.println(i);
            }
    }
    static void  quicksort(int a[],int p,int r)
    {
     int q;
     if(p<r)
     {
            Random random = new Random();
            int y = p+random.nextInt(r-p+1);
            int temp = a[y];
            a[y]=a[r];
            a[r]=temp;
            q = partition(a,p,r);
            quicksort(a,p,q-1);
            quicksort(a,q+1,r);
     }
    }
    static int partition(int a[],int p,int r)
    {        
        int x=a[r];
        int i=p-1;
        for (int j = p; j <= r-1; j++) {
            if(a[j]<=x)
            {
                i++;
                swap(a,i,j);
            }                       
        }        
        swap(a,i+1,r);      
        return i+1;
    }
    static void swap(int a[],int x,int y)
    {
        int t=a[x];
        a[x]=a[y];
        a[y]=t;
    }
}

Answer 1

理论复杂性保持不变。 O(nlogn) 平均情况和 O(n^2) 最坏情况。

如果选择随机基准不是为了消除 O(n^2) 的最坏情况性能 - 这仍然可能发生，概率很低。
这个想法是为了让算法更能抵抗恶意输入的攻击。<​​/p>

当枢轴是伪随机选择时，很难预测哪个数组会导致最坏情况的行为，所以如果有人想攻击我们的程序，并导致它的工作速度显着变慢——这对他来说会更难去做。

另一个问题是确保如果您的数据倾向于以某种模式出现 - 最坏的情况不会一遍又一遍地重复(很有可能)。

作为旁注，像“经典”快速排序那样将第一个(或最后一个)元素作为枢轴是一个坏主意，因为数组在现实生活中的应用程序被排序或几乎排序的概率远高于一个会期望，导致算法经常陷入最坏的情况行为。有关它的更多信息可以在此线程中找到: Why are we interested in how long it takes to sort a file that is already sorted?