首页 > 代码库 > 算法导论-排序（二）快速排序、随机化快速排序
算法导论-排序（二）快速排序、随机化快速排序
目录
1、本文介绍
2、快速排序
3、随机化快速排序
4、完整源码
5、参考资料
内容
1、本文介绍
主要内容分为两部分，一部分是介绍快速排序算法，分析其在最好、最坏以及最好最差交替出现情况下的算法效率；另一部分则是介绍随机化快排算法，以及分析其算法复杂度。最后给出c++实现代码。
2、快速排序
快速排序也是基于分治思想，首先把要排序的数组分为两份，然后再分别对分好的子数组进行快速排序。当子数组为1个元素时递归介绍，排序完成。快速排序属于“原地排序”，就是说在原有的数组内存上排序、不占用其他内存。归并排序就不一样，它则需要额外的空间来进行归并排序操作。下图是快速排序的分治思想：
由上图可以知道，快速排序里面最关键的就是第一步：分化（Partition）的步骤，这是该算法处理问题的核心。所以我们可以把快排看成是递归地划分数组，就像归并排序是递归地合并数组一样。关于Paritition的具体算法，目前有好几种，其伪代码稍有不同但是它们的原理都是一样的。当然最重要的一点是分化（Partition）的算法复杂度都是线性的，也就是O(n)。下面是分化（Partition）的一种伪码：
1 Partition(A,p,q)2 x <- A[p] //选第一个为主元3 i <- p4 for j <- p+1 to q5 do if A[j] < x //小于主元的数据放在左边6 then i <- i+17 exch A[i] <-> A[j] // 交换A[i] A[j] 8 exch A[p] <-> A[i] // 交换9 return i //返回划分好后主元索引
分划好后就是简单的递归，下面是快排的伪代码：
1 QuickSort(A,p,q)2 if p < q //不满足就介绍递归3 then r <- Partition(A,p,q) //分划4 QuickSort(A，p , r-1) //递归快排左子数组5 QuickSort(A , r+1 ,q) //递归快排右子数组
接下来分析快排的算法效率
1）最坏情况下分析
当输入序列是正序或者是反序的时候，效率最坏，这时效率是Θ(n2)
2) 最优情况下分析
其他情况下的算法效率趋向于Θ（nlgn）
那么我们如何保证我们总是效率处于最优情况下的呢？这就是随机化快速排序需要解决的问题。
3、随机化快速排序
我们已经知道，若输入本身已被排序，那么对于快排来说就糟了。那么如何避免这样的情况？一种方法时随机排列序列中的元素；另一种方法时随机地选择主元（pivot）。这便是随机化快速排序的思想，这种快排的好处是：其运行时间不依赖于输入序列的顺序。
经分析， 随机化快排的算法效率是Θ(nlgn)。
实现：我们只需在选取主元时加入随机因素即可。其他与快排一样
下面是分化（Partition）编程（c++）实现
1 int Random_Partition(vector<T> &A,int p,int q)2 {3 int i=rand()%(q-p)+p; //此行与快排不同、加入随机数参数器4 Swap(A[i],A[p]); //此行与快排不同、随机选取主元5 return Partition(A,p,q);//此次与快速排序一样6 }
// 随机化快速排序
1 void Random_Quick_Sort(vector<T> &A,int p,int q)2 {3 if (p<q)4 {5 int i=Random_Partition(A,p,q);6 Random_Quick_Sort(A,p,i-1);7 Random_Quick_Sort(A,i+1,q);8 }9 }
4、完整源码
下面源码包含之前讨论过的插入排序、归并排序算法。最后给出时间比较
CTimer.h (测试间的头文件实现，不懂无需纠结)
1 #ifndef CTIMER_HH 2 #define CTIMER_HH 3 class CTimer 4 { 5 public: 6 CTimer() 7 { 8 QueryPerformanceFrequency(&m_Frequency); 9 Start();10 }11 void Start()12 {13 QueryPerformanceCounter(&m_StartCount);14 }15 double End()16 {17 LARGE_INTEGER CurrentCount;18 QueryPerformanceCounter(&CurrentCount);19 return double(CurrentCount.LowPart - m_StartCount.LowPart) *1000/ (double)m_Frequency.LowPart;20 }21 void ShowNow()22 {23 LARGE_INTEGER CurrentCount;24 QueryPerformanceCounter(&CurrentCount);25 cout<<"Timer Count is:"<<double(CurrentCount.LowPart - m_StartCount.LowPart)*1000 / (double)m_Frequency.LowPart<<endl;26 }27 private:28 LARGE_INTEGER m_Frequency;29 LARGE_INTEGER m_StartCount;30 };31 #endif
Sort.h (排序算法[插入排序、归并排序、快速排序、随机化快速排序]实现头文件)
1 #ifndef SORT_HH 2 #define SORT_HH 3 template<typename T >//带模板 4 class Sort 5 { 6 public: 7 void insertion_sort(vector<T> &A);//插入排序 8 void merge_sort(vector<T> &A,int p,int r);//归并排序 9 void print_element(vector<T> A);//打印数组 10 void Quick_Sort(vector<T> &A,int p,int q);//快速排序 11 int Partition(vector<T> &A,int p,int q);//分划 12 void Swap(T &m,T &n);//交换数据 13 void Random_Quick_Sort(vector<T> &A,int p,int q);//随机化快速排序 14 int Random_Partition(vector<T> &A,int p,int q);//随机化分划 15 private: 16 void merge(vector<T> &A,int p,int q,int r);// 归并排序子程序 17 }; 18 template<typename T>//插入排序 19 void Sort<T>::insertion_sort(vector<T> &A) 20 { 21 int i,j; 22 T key; 23 int len=A.size(); 24 for (j=1;j<len;j++) 25 { 26 i=j-1; 27 key=A[j]; 28 while (i>=0&&A[i]>key) 29 { 30 A[i+1]=A[i]; 31 i--; 32 } 33 A[i+1]=key; 34 } 35 } 36 37 template<typename T>// 归并排序子程序 38 void Sort<T>::merge(vector<T> &A,int p,int q,int r) 39 { 40 int n1=q-p+1; 41 int n2=r-q; 42 T *L=new T[n1+1]; 43 T *R=new T[n2+1]; 44 45 for (int i=0;i<n1;i++) 46 L[i]=A[i+p]; 47 for (int i=0;i<n2;i++) 48 R[i]=A[i+q+1]; 49 50 L[n1]=R[n2]=INT_MAX; 51 52 int i=0,j=0; 53 for (int k=p;k<=r;k++) 54 { 55 if (L[i]>R[j]) 56 { 57 A[k]=R[j]; 58 j++; 59 } 60 else 61 { 62 A[k]=L[i]; 63 i++; 64 } 65 } 66 67 delete[] L; 68 delete[] R; 69 70 } 71 72 template<typename T>//归并排序 73 void Sort<T>::merge_sort(vector<T> &A,int p,int r) 74 { 75 if (p<r) 76 { 77 int mid=(p+r)/2; 78 merge_sort(A,p,mid); 79 merge_sort(A,mid+1,r); 80 merge(A,p,mid,r); 81 } 82 } 83 84 template<typename T>//交换数据 85 void Sort<T>::Swap(T &m,T &n) 86 { 87 T tmp; 88 tmp=m; 89 m=n; 90 n=tmp; 91 } 92 93 /***********快速排序分划程序*************/ 94 template<typename T> 95 int Sort<T>::Partition(vector<T> &A,int p,int q) 96 { 97 T x=A[p]; 98 int i=p; 99 for (int j=p+1;j<=q;j++)100 {101 if (A[j]<x)102 {103 i=i+1;104 Swap(A[i],A[j]);105 }106 }107 Swap(A[p],A[i]);108 return i;109 }110 template<typename T>//快速排序111 void Sort<T>::Quick_Sort(vector<T> &A,int p,int q)112 {113 if(p<q)114 {115 int i=Partition(A,p,q);116 Quick_Sort(A,p,i-1);117 Quick_Sort(A,i+1,q);118 }119 }120 121 template<typename T>//随机化快速排序分划程序122 int Sort<T>::Random_Partition(vector<T> &A,int p,int q)123 {124 int i=rand()%(q-p)+p;125 Swap(A[i],A[p]);126 return Partition(A,p,q);127 }128 129 template<typename T>//随机化快速排序130 void Sort<T>::Random_Quick_Sort(vector<T> &A,int p,int q)131 {132 if (p<q)133 {134 int i=Random_Partition(A,p,q);135 Random_Quick_Sort(A,p,i-1);136 Random_Quick_Sort(A,i+1,q);137 }138 }139 140 template<typename T>//打印数组141 void Sort<T>::print_element(vector<T> A)142 {143 int len=A.size();144 for (int i=0;i<len;i++)145 {146 std::cout<<A[i]<<" ";147 }148 std::cout<<std::endl;149 }150 #endif
Sort_main.cpp （测试主程序）
1 #include <iostream> 2 #include <vector> 3 #include <time.h> 4 #include <Windows.h> 5 using namespace std; 6 #include "Sort.h" 7 #include "CTimer.h" 8 9 #define N 10 //排序数组大小10 // 随机参数排序数组11 void Random(vector<int> &a,int n) 12 { 13 int i=0; 14 srand( (unsigned)time( NULL ) ); 15 while(i<n) 16 { 17 a[i++]=rand(); 18 } 19 } 20 int main()21 {22 Sort<int> sort1;23 CTimer t;24 vector<int > vec_int(N);25 Random(vec_int,N);26 cout<<"源数组：";27 sort1.print_element(vec_int);28 t.Start();29 sort1.Quick_Sort(vec_int,0,vec_int.size()-1);30 cout<<"快速排序:"<<t.End()<<"ms"<<endl;31 sort1.print_element(vec_int);32 Random(vec_int,N);33 t.Start();34 sort1.Random_Quick_Sort(vec_int,0,vec_int.size()-1);35 cout<<"随机化快速排序:"<<t.End()<<"ms"<<endl;36 sort1.print_element(vec_int);37 Random(vec_int,N);38 t.Start();39 sort1.insertion_sort(vec_int);40 cout<<"插入排序:"<<t.End()<<"ms"<<endl;41 sort1.print_element(vec_int);42 Random(vec_int,N);43 t.Start();44 sort1.merge_sort(vec_int,0,vec_int.size()-1);45 cout<<"归并排序:"<<t.End()<<"ms"<<endl;46 sort1.print_element(vec_int);47 48 system("PAUSE");49 return 0;50 }
输出：
排序算法时间比较：
| 数组大小 | 快速排序（ms） | 随机化快速排序(ms) | 插入排序（ms） | 归并排序(ms) |
| 10 | 0.0054523 | 0.00673552 | 0.00481085 | 0.0189227 |
| 100 | 0.108084 | 0.107763 | 0.377492 | 0.232845 |
| 1000 | 1.71427 | 1.47212 | 49.5864 | 2.67323 |
| 10000 | 34.795 | 19.2226 | 3542.74 | 30.3318 |
| 100000 | 232.691 | 233.02 | 352846 | 350.414 |
| 1000000 | 3032.3 | 3273.46 | ......（太大、没测） | 4017.02 |
自我小结：对随机产生的数组进行排序，1）可以发现插入排序没有优势、特别是数组比较大时耗时太多；2）快速排序、随机化快速排序、归并排序性能不错，然而两种快排比归并排序性能好点；3）当数据量变大时，可以看出性能排序为快速排序、随机化快速排序、归并排序、插入排序；4）由于这里的数组是由随机数产生的，没有显示出随机化快速排序的优势，但是当数组为已排序情况下随机化快排将比快排性能好。
5、参考资料
【1】http://blog.csdn.net/xyd0512/article/details/8259382
【2】http://blog.csdn.net/kenden23/article/details/14558231
【3】http://www.cnblogs.com/lidabo/archive/2013/01/08/2850418.html
算法导论-排序（二）快速排序、随机化快速排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。