实现随机快速排序算法

Question

CLRS 告诉我们用 A[i] 交换 A[r]，其中 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) 的最坏情况性能 - 这种情况仍然可能发生，概率很低。
这个想法是为了让算法更能抵御恶意输入的攻击。

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

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

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

Answer 2

当我们谈论某些算法的Big-O复杂度时。通常我们谈论的是理论上的平均时间复杂度。尽管您必须意识到，在最坏的情况下，时间复杂度可能比平均水平差得多。

例如，快速排序的平均计算复杂度为 O(n log n)。但是最坏的情况是 O(n2) 当你的原始数组完全颠倒并且你选择了错误的主元时。

实现随机快速排序算法

Implementing a randomized quick sort algorithm

algorithm

quicksort

clrs