最坏情况快速排序的运行时间为Ο(nlgn)的算法

思想方法与思考过程：

快速排序对主元的划分决定了其运行时间，如果最坏是Ο(nlgn)，那么就不允许出现极端划分情况。因为我们学习了最坏时间了线性的选择算法，我们何不利用其每次选择都选中位数作为主元的方法来避免极端情况的发生？既然每次都选择中位数作为主元，那么其递归运行时间总是T(n)=2T(n/2)+Ο(n) 这样根据主方法case 2 知道T(n)=Ο(nlgn)。

完整代码与详细解释：

[cpp] view plaincopyprint?

1. #include <iostream>  
2. #include <time.h>  
3. using namespace std;  
4. const n=100;  
5. //创建一个装有数组A以每5个元素为1组共n/5组，每组的中位数放入到数组B中，组成一组含有n/5个中位数的数组B  
6. int Find(int A[n],int p,int r);//递归当前数组A中从p到r个元素，以找到辅助中位数数组B的中位数。  
7. int PARTITION(int A[],int p,int r,int t)//t代表中位数数组B中的中位数，这里t代表为主元。  
8. {  
9.     int i=p-1,k=0;  
10.     for (int j=p;j<=r;j++)  
11.     {  
12.         if (A[j]<t)//将比主元t大的元素交换到数组A的右边去，比主元t小的到数组A的左边。  
13.         {  
14.             i++;  
15.             swap(A[i],A[j]);  
16.         }  
17.         if (A[j]==t)//如果A[j]等于主元  
18.         {  
19.             k=j;//那么记录下主元在A中的位置。  
20.         }  
21.     }  
22.     swap(A[i+1],A[k]);//完成划分操作，主元左边的元素都小于主元，主元右边的元素都大于主元。  
23.     return i+1;  
24. }  
25. int SELECT(int A[],int p,int r,int i)//i表示第i小的数。  
26. {  
27.     if (p>=r)  
28.     {  
29.         return A[p];  
30.     }  
31.     int t=Find(A,p,r);//返回的t代表辅助数组B的中位数。      
32.     int q=PARTITION(A,p,r,t);  
33.     int k=q-p+1;  
34.     if (i==k)  
35.     {  
36.         return A[q];  
37.     }  
38.     else if(i<k)  
39.     {  
40.         return SELECT(A,p,q-1,i);  
41.     }  
42.     else return SELECT(A,q+1,r,i-k);  
43. }  
44. int Find(int A[n],int p,int r)  
45. {      
46.     int key=0,t=0,m=r-p+1,h=0;  
47.     if (m%5==0)//如果当前数组A的大小能被5整除，那么这以5个元素为一组的m/5组数，没有余数那一组  
48.     {  
49.         h=m/5;  
50.     }  
51.     else//否则，应该加上含有余数的那一组。  
52.     {  
53.         h=m/5+1;  
54.     }  
55.     int *B=new int[h];  
56.     for(int j=0;j<h;j++)  
57.     {  
58.         B[j]=0;  
59.     }  
60.     for (int k=0;k<h;k++)//5个数一组，共h组。进行插入排序。  
61.     {//经过最多h=n/5+1次循环，那么总共循环了25h=25(n/5+1)=5n+25=O(n)次  
62.         for (int j=t+1+p;j<=5+t+p&&j!=r+2;j++)//h组中每组进行插入排序。注意加上数组初始坐标p(当前数组A的初值坐标)+t(在p基础上每5个为1组)  
63.         {//运行时间分析：5个一组运行插入排序，每次插入排序需要的时间是O(n^2)=5^2=25是基于固定划分的固定常数  
64.             key=A[j-1];  
65.             int i=j-1;  
66.             while (i>t+p&&A[i-1]<key)  
67.             {  
68.                 A[i]=A[i-1];  
69.                 i=i-1;  
70.             }  
71.             A[i]=key;  
72.         }  
73.         t+=5;//进入下一个5个元素为一组的插入排序  
74.     }  
75.     k=0;  
76.     for (int i=0;i<h&&k<h;i++)//经过最多h=n/5+1次循环(O(n))，将当前数组A中的每组的中位数依次放入到B中  
77.     {  
78.         if (i<h-1)  
79.         {  
80.             B[k]=A[2+5*i+p];  
81.             k++;  
82.             continue;  
83.         }  
84.         if(m%5!=0)  
85.         {  
86.             B[k]=A[5*i+p+(m%5)/2];  
87.         }  
88.         else   
89.         {  
90.             B[k]=A[2+5*i+p];  
91.             k++;  
92.         }  
93.     }  
94.     if (h==1)  
95.     {  
96.         return B[0];//当辅助数组B只剩下一个数时，那么这个数就是中位数的中位数。  
97.     }  
98.     else  
99.     {  
100.         return SELECT(B,0,h-1,(h-1)/2+1);//如果数组B元素个数是偶数，那么取数组B中的较小值。  
101.     }  
102. }  
103. void QUICKSORT(int A[],int p,int r)//选择SELECT函数和划分PARTITION函数的时间复杂度都是O(n),又因为总是取中位数作为主元划分的，所以递归函数时间复杂度为T(n)=2T(n/2)+O(n)=>T(n)=O(nlgn)  
104. {  
105.     if (p<r)  
106.     {  
107.         int t=SELECT(A,p,r,(r+p)/2-p+1);//(r+p)/2-p+1=(r-p)/2+1 当前数组A的第一个元素和最后一个元素的位置下标差+1就是中位数  
108.         int q=PARTITION(A,p,r,t);//返回的q的位置对应的值A[q]就是当前数组A从p到r的中间值，如果是偶数个元素那么取较小中间值。  
109.         QUICKSORT(A,p,q-1);//以中间值A[q]作为主元划分后，QUICKSORT(A,p,q-1)左半部分是小于等于A[q]的。  
110.         QUICKSORT(A,q+1,r);//QUICKSORT(A,q+1,r)右半部分是大于等于A[q]的。  
111.     }  
112. }  
113. void main()  
114. {  
115.     int A[n]={0};  
116.     //随机输入数组  
117.     srand( (unsigned)time( NULL ) );  
118.     cout<<"排序前："<<endl;  
119.     for (int i=0;i<n;i++)  
120.     {  
121.         A[i]=rand()%100;  
122.         cout<<A[i]<<"\t";  
123.     }  
124.     cout<<endl;  
125.     QUICKSORT(A,0,n-1);  
126.     cout<<"排序后："<<endl;  
127.     for (i=0;i<n;i++)  
128.     {  
129.         cout<<A[i]<<"\t";  
130.     }  
131.     cout<<endl;  
132. }