快速排序的思想大體來說比較簡單，就是從數(shù)組中挑選一個(gè)數(shù)字當(dāng)做樞紐，然后將比樞紐大的和比樞紐小的分別放在樞紐的兩邊，再遞歸地對兩邊進(jìn)行操作，從而進(jìn)行分治解決問題。平均情況下快速排序是復(fù)雜度為$O(nlogn)$，可是有時(shí)候復(fù)雜度會退化為$O(n^2)$，這與我們?nèi)绾芜x擇樞紐以及如何將數(shù)組進(jìn)行劃分有關(guān)。

總共有兩種情況下復(fù)雜度會退化：

數(shù)組大體有序：這個(gè)時(shí)候如果我們樞紐選擇的不夠好，那么數(shù)組的一邊將會比較大，一邊將會比較小，最嚴(yán)重的時(shí)候每次只能將規(guī)模減一，則復(fù)雜度將會變成$T(n)=T(n?1)+n$，即$T(n)=n^2$。解決這個(gè)問題的方法就是合理的選擇樞紐，例如選擇數(shù)組頭部、尾部、中間三個(gè)數(shù)字的平均值，這種方法就能有有效解決這個(gè)問題。我們一般將樞紐放在數(shù)組的頭部（只需要交換選擇的樞紐和原本位于樞紐頭部的元素即可），這樣做可以方便我們進(jìn)行劃分。

數(shù)組中有很多一模一樣的數(shù)字：這樣同樣會產(chǎn)生每次只能將規(guī)模減小很少的情況，最壞的時(shí)候復(fù)雜度也將退化為$O(n^2)$。這種問題的產(chǎn)生我們無法通過有效的選擇樞紐解決，只能夠通過劃分的時(shí)候使得即使數(shù)組中的元素都等于樞紐我們?nèi)耘f能夠?qū)?shù)組大概分成相等的兩部分。

常見的有以下劃分方法：

從一邊進(jìn)行劃分

? 大概的思想就是把第一個(gè)元素當(dāng)做樞紐，然后使用一個(gè)指針保存分界點(diǎn)，指針的左邊是小于樞紐的元素，指針的右邊是大于等于樞紐的元素（必須有一邊支持等于，否則劃分將會卡住）。

? 將指針初始化在數(shù)組頭部，遍歷后面的元素，如果比樞紐小就將指針向后移動一位，然后將該位置的元素和遍歷到的元素交換。否則就繼續(xù)向后遍歷。這樣做可以成功的原因是任何時(shí)刻指針后面的元素都是大于等于樞紐的元素，通過交換就將小于樞紐的元素放在了指針之前，從而完成劃分。

實(shí)現(xiàn)代碼

void QuickSort(T* a,int l,int r) {if(r-l<2) return;//從一邊劃分int index=l;T x=a[l];for(int i=l+1;i<r;++i){if(a[i]<x)swap(a[++index],a[i]);}swap(a[index],a[l]);QuickSort(a,l,index); QuickSort(a,index+1,r); ｝

雖然這種方法實(shí)現(xiàn)起來比較簡單，但是他不能夠解決出現(xiàn)大量重復(fù)元素復(fù)雜度提升的問題。

從兩邊進(jìn)行劃分

• 空穴法

  我們先將樞紐元素取出數(shù)組，然后用兩個(gè)指針分別指向數(shù)組頭部和數(shù)組尾部，先從尾部找比樞紐元素小的元素，找到以后放在數(shù)組頭部因?yàn)閷屑~元素取出形成的空穴中，此時(shí)指向數(shù)組尾部的指針?biāo)赶虻脑乇蝗∽咝纬煽昭?#xff0c;再從頭部找比樞紐大的元素，找到以后再放在尾部形成的空穴中。如此反復(fù)，直到兩個(gè)指針相遇，然后再將樞紐放在最后的這個(gè)空穴中，完成劃分。

  實(shí)現(xiàn)代碼

  void QuickSort(T* a,int l,int r){if(r-l<2) return;//空穴法int i=l,j=r-1;T x=a[l];while(i<j){while(i<j && a[j]>x) --j; a[i]=a[j];while(i<j && a[i]<=x) ++i;a[j]=a[i];}a[i]=x;QuickSort(a,l,i); QuickSort(a,i+1,r);}

  這中方法我們同樣必須在一邊允許等號，因此也可能出現(xiàn)復(fù)雜度退化的問題

• 直接交換

  當(dāng)然我們也可以直接進(jìn)行交換而不使用空穴，一種簡單的實(shí)現(xiàn)方法

  void QuickSort(T* a,int l,int r) {if(r-l<2) return;int i=l+1,j=r-1;T x=a[l];while(i<=j){while(i<r && a[i]<=x) ++i;while(j>l && a[j]>x) --j;if(i<j) swap(a[i],a[j]);}swap(a[l],a[j]);QuickSort(a,l,j);QuickSort(a,i,r); ｝

  然而這種方法依舊不能夠解決問題（不會采用），因此我們需要進(jìn)行一些變形

  實(shí)現(xiàn)代碼

  void QuickSort(T* a,int l,int r) {if(r-l<2) return;int i=l-1,j=r;T pivot = a[l];while(i<j){do ++i; while(a[i] < pivot);do --j; while(a[j] > pivot);if(i < j) swap(a[i],a[j]);}QuickSort(a,l,j+1); QuickSort(a,j+1,r); ｝

為什么這樣做就可以解決重復(fù)元素的問題呢？這里和上面方法最大的不同就在于我們在劃分的時(shí)候沒有使用等號。這樣的話如果遇到和樞紐相等的元素的時(shí)候我們就移動然后越過這個(gè)位置。使用$do$ $while;$結(jié)構(gòu)就是為了能夠跨越和樞紐相等的元素。如果整個(gè)數(shù)組都是相等的話雖然我們多進(jìn)行一些交換，但是有效地將數(shù)組劃分成了差不多相等的兩部分。
對于代碼的理解，很重要的一點(diǎn)就是將$i=l?1$。剛開始我覺得這一點(diǎn)沒有很重要所以自己將其改為了$i=l$，然后最后將樞紐元素放在中間。但是在測試的時(shí)候我發(fā)現(xiàn)對于有些數(shù)據(jù)會出錯(cuò)。仔細(xì)推敲數(shù)據(jù)以后發(fā)現(xiàn)，$i=l?1$的意義不僅僅在于第一個(gè)$do()while$結(jié)構(gòu)可以將樞紐元素計(jì)算進(jìn)去，更重要的是一個(gè)哨兵的作用。因?yàn)楹竺嫖覀冞M(jìn)行移動指針的時(shí)候并沒有判斷指針是否越界。對于右邊的指針無論如何一定會停下來，因?yàn)樗淖筮呏辽龠€有一個(gè)和樞紐元素相等的元素（樞紐元素本身），但是如果左邊我們剛開始的時(shí)候跳過了樞紐元素，那么如果在數(shù)組末尾的話就會越界。只有讓左邊剛開始為$i=l?1$，那么指針至少會停在樞紐元素的位置。如果發(fā)生了交換的話，那么指針也一定會停在交換時(shí)右邊指針位置的前面。還有一點(diǎn)就是第12行區(qū)間分割為[l,j+1) [j+1,r)而不是[l,j),[j,r)，因?yàn)楹竺孢@種做法有可能導(dǎo)致左邊[l,j)的區(qū)間長度為0，這樣將會導(dǎo)致棧溢出。產(chǎn)生這種現(xiàn)象的原因主要是樞紐元素選擇的不恰當(dāng)，對于選擇第一個(gè)元素作為樞紐來講，j一定是小于r-1的（因?yàn)榈谝淮慰隙〞ㄗ?#xff09;，所以不用擔(dān)心j+1等于r。如果樞紐選擇的比較恰當(dāng)，就不會出現(xiàn)這種問題。

? 上面的這種做法沒有將樞紐元素放在中間，但是因?yàn)樗缓ε轮貜?fù)元素，所以不用擔(dān)心問題的規(guī)模不減小而產(chǎn)生棧溢出。

通過劃分解決了上面的問題以后我們就可以得到一個(gè)復(fù)雜度挺優(yōu)秀的快速排序了。

實(shí)現(xiàn)代碼

#include <iostream>using namespace std;typedef double T;T* CreatList(int &n) {printf("n="); scanf("%d",&n);T* ret = new T[n];for(int i=0;i<n;++i){cin>>ret[i];}return ret; }void Init(T* a,int l,int r) {int mid=(l+r)>>1;if(a[mid] < a[l]) swap(a[mid],a[l]);if(a[mid] < a[r-1]) swap(a[mid],a[r-1]);if(a[l] > a[r-1]) swap(a[l],a[r-1]);return; }void QuickSort(T* a,int l,int r) {if(r-l<2) return;Init(a,l,r);//將首部、尾部、中間三個(gè)數(shù)中的中值放在開頭int i=l-1,j=r;T pivot = a[l];while(i<j){do ++i; while(a[i] < pivot);do --j; while(a[j] > pivot);if(i < j) swap(a[i],a[j]);}QuickSort(a,l,j+1); QuickSort(a,j+1,r); }void Show(T* a,int n) {for(int i=0;i<n;++i){cout<<a[i]<<" ";}cout<<endl; }int main() {int n;T* a=CreatList(n);QuickSort(a,0,n);cout<<"經(jīng)過排序之后:"<<endl;Show(a,n);delete[] a;return 0; }

為了驗(yàn)證是否我們的確對算法的效率進(jìn)行了提高，我編寫了測試程序：（單位為$S$，環(huán)境為$Ubuntu18.04$）

數(shù)據(jù)規(guī)模1e5亂序1e6亂序1e7亂序5e4重復(fù)5e4有序

一側(cè)劃分+取中值	0.021184	0.255226	2.913669	2.964905	0.005573
空穴法劃分+取中值	0.014865	0.172306	1.980930	3.135060	0.002652
兩側(cè)直接劃分+取中值	0.017033	0.195318	2.236171	0.004814	0.002670
兩側(cè)直接劃分	0.016239	0.189592	2.178169	0.004700	2.622307

? 為了減少運(yùn)行時(shí)操作系統(tǒng)的影響，每個(gè)數(shù)據(jù)規(guī)模運(yùn)行我都運(yùn)行十次然后取平均值。

? 雖然仍舊可能還有數(shù)據(jù)本身的影響，但是我們也能夠大概看出來一個(gè)大體的變化規(guī)律。當(dāng)數(shù)據(jù)為亂序的時(shí)候空穴法是比較優(yōu)秀的，但是當(dāng)出現(xiàn)重復(fù)元素時(shí)，兩側(cè)直接劃分的方法碾壓前面兩種方法。當(dāng)數(shù)據(jù)大體是有序的時(shí)候如果我們選取樞紐直接選擇第一個(gè)其時(shí)間復(fù)雜度也是可怕的。

? 因此綜合考慮我們采用第三種方法是比較好的。

測試程序代碼

#include <iostream> #include <ctime> #include <cstdio> #include <fstream> #include <cstdlib>using namespace std;typedef double T; typedef void (*FP)(T*,int,int); //定義函數(shù)指針數(shù)組類型void CreatData() {int n=10;FILE* file=fopen("TestFile","w");fprintf(file,"%d\n",n);int t;srand(t);for(int i=0;i<n;++i){t=rand();fprintf(file,"%d ",rand()%10);}fclose(file);return ; }T* CreatList(int &n) {//printf("n=");//CreatData();ifstream in("TestFile");in >> n;T* ret = new T[n];for(int i=0;i<n;++i){in>>ret[i];}in.close();return ret; }void Init(T* a,int l,int r) {int mid=(l+r)>>1;if(a[mid] > a[l]) swap(a[mid],a[l]);if(a[mid] > a[r-1]) swap(a[mid],a[r-1]);if(a[l] > a[r-1]) swap(a[l],a[r-1]);return; }void QuickSort1(T* a,int l,int r) {if(r-l<2) return;Init(a,l,r);//將首部、尾部、中間三個(gè)數(shù)中的中值放在開頭//從一邊劃分int index=l;T x=a[l];for(int i=l+1;i<r;++i){if(a[i]<x)swap(a[++index],a[i]);}swap(a[index],a[l]);QuickSort1(a,l,index); QuickSort1(a,index+1,r); }void QuickSort2(T* a,int l,int r) {if(r-l<2) return;Init(a,l,r);//將首部、尾部、中間三個(gè)數(shù)中的中值放在開頭//空穴法int i=l,j=r-1;T x=a[l];while(i<j){while(i<j && a[j]>x) --j; a[i]=a[j];while(i<j && a[i]<=x) ++i;a[j]=a[i];}a[i]=x;QuickSort2(a,l,i); QuickSort2(a,i+1,r); }void QuickSort3(T* a,int l,int r) {if(r-l<2) return;Init(a,l,r);//將首部、尾部、中間三個(gè)數(shù)中的中值放在開頭int i=l-1,j=r;T pivot = a[l];while(i<j){do ++i; while(a[i] < pivot);do --j; while(a[j] > pivot);if(i < j) swap(a[i],a[j]);}QuickSort3(a,l,j+1); QuickSort3(a,j+1,r); }void QuickSort4(T* a,int l,int r) {if(r-l<2) return;int i=l-1,j=r;T pivot = a[l];while(i<j){do ++i; while(a[i] < pivot);do --j; while(a[j] > pivot);if(i < j) swap(a[i],a[j]);}QuickSort4(a,l,j+1); QuickSort4(a,j+1,r); }void Show(T* a,int n) {for(int i=0;i<n;++i){cout<<a[i]<<" ";}cout<<endl; }void Test(FP fp[]) {for(int i=0;i<4;++i){clock_t S,E;int Time = 10;double sum=0;for(int j=0;j<Time;++j){int n;T* a=CreatList(n);S=clock();fp[i](a,0,n);E=clock();sum+=(double)(E-S)/CLOCKS_PER_SEC;//cout<<"經(jīng)過排序之后:"<<endl;//Show(a,n);delete[] a;}printf("QuickSort%d's times=%f\n",i+1,sum/Time);} }int main() {FP fp[4] = {QuickSort1,QuickSort2,QuickSort3,QuickSort4};Test(fp);return 0; }

總結(jié)

以上是生活随笔為你收集整理的快速排序详解+各种实现方式的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。