快速排序詳解+各種實現方式

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

總共有兩種情況下復雜度會退化：

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

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

常見的有以下劃分方法：

  1. 從一邊進行劃分

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

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

    實現代碼

    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);
｝

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

  1. 從兩邊進行劃分

  • 空穴法

    我們先將樞紐元素取出數組，然后用兩個指針分別指向數組頭部和數組尾部，先從尾部找比樞紐元素小的元素，找到以后放在數組頭部因為將樞紐元素取出形成的空穴中，此時指向數組尾部的指針所指向的元素被取走形成空穴，再從頭部找比樞紐大的元素，找到以后再放在尾部形成的空穴中。如此反復，直到兩個指針相遇，然后再將樞紐放在最后的這個空穴中，完成劃分。

    實現代碼

    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);}

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

  • 直接交換

    當然我們也可以直接進行交換而不使用空穴，一種簡單的實現方法

    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);
｝

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

    實現代碼

    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);
｝

為什么這樣做就可以解決重復元素的問題呢？這里和上面方法最大的不同就在于我們在劃分的時候沒有使用等號。這樣的話如果遇到和樞紐相等的元素的時候我們就移動然后越過這個位置。使用dododo while;while;while;結構就是為了能夠跨越和樞紐相等的元素。如果整個數組都是相等的話雖然我們多進行一些交換，但是有效地將數組劃分成了差不多相等的兩部分。
對于代碼的理解，很重要的一點就是將i=l?1i=l-1i=l?1。剛開始我覺得這一點沒有很重要所以自己將其改為了i=li=li=l，然后最后將樞紐元素放在中間。但是在測試的時候我發現對于有些數據會出錯。仔細推敲數據以后發現，i=l?1i=l-1i=l?1的意義不僅僅在于第一個do()whiledo() whiledo()while結構可以將樞紐元素計算進去，更重要的是一個哨兵的作用。因為后面我們進行移動指針的時候并沒有判斷指針是否越界。對于右邊的指針無論如何一定會停下來，因為它的左邊至少還有一個和樞紐元素相等的元素（樞紐元素本身），但是如果左邊我們剛開始的時候跳過了樞紐元素，那么如果在數組末尾的話就會越界。只有讓左邊剛開始為i=l?1i=l-1i=l?1，那么指針至少會停在樞紐元素的位置。如果發生了交換的話，那么指針也一定會停在交換時右邊指針位置的前面。還有一點就是第12行區間分割為[l,j+1) [j+1,r)而不是[l,j),[j,r)，因為后面這種做法有可能導致左邊[l,j)的區間長度為0，這樣將會導致棧溢出。產生這種現象的原因主要是樞紐元素選擇的不恰當，對于選擇第一個元素作為樞紐來講，j一定是小于r-1的（因為第一次肯定會卡住），所以不用擔心j+1等于r。如果樞紐選擇的比較恰當，就不會出現這種問題。

? 上面的這種做法沒有將樞紐元素放在中間，但是因為他不害怕重復元素，所以不用擔心問題的規模不減小而產生棧溢出。

通過劃分解決了上面的問題以后我們就可以得到一個復雜度挺優秀的快速排序了。

實現代碼

#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);//將首部、尾部、中間三個數中的中值放在開頭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<<"經過排序之后:"<<endl;Show(a,n);delete[] a;return 0;
}

為了驗證是否我們的確對算法的效率進行了提高，我編寫了測試程序：（單位為SSS，環境為Ubuntu18.04Ubuntu18.04Ubuntu18.04）

數據規模1e5亂序1e6亂序1e7亂序5e4重復5e4有序
一側劃分+取中值0.0211840.2552262.9136692.9649050.005573
空穴法劃分+取中值0.0148650.1723061.9809303.1350600.002652
兩側直接劃分+取中值0.0170330.1953182.2361710.0048140.002670
兩側直接劃分0.0162390.1895922.1781690.0047002.622307

? 為了減少運行時操作系統的影響，每個數據規模運行我都運行十次然后取平均值。

? 雖然仍舊可能還有數據本身的影響，但是我們也能夠大概看出來一個大體的變化規律。當數據為亂序的時候空穴法是比較優秀的，但是當出現重復元素時，兩側直接劃分的方法碾壓前面兩種方法。當數據大體是有序的時候如果我們選取樞紐直接選擇第一個其時間復雜度也是可怕的。

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

測試程序代碼

#include <iostream>
#include <ctime>
#include <cstdio>
#include <fstream>
#include <cstdlib>using namespace std;typedef double T;
typedef void (*FP)(T*,int,int);  //定義函數指針數組類型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);//將首部、尾部、中間三個數中的中值放在開頭//從一邊劃分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);//將首部、尾部、中間三個數中的中值放在開頭//空穴法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);//將首部、尾部、中間三個數中的中值放在開頭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<<"經過排序之后:"<<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;
}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/383673.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/383673.shtml
英文地址，請注明出處：http://en.pswp.cn/news/383673.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

C++的單例模式與線程安全單例模式（懶漢/餓漢）

C++的單例模式與線程安全單例模式（懶漢/餓漢）

https://www.cnblogs.com/qiaoconglovelife/p/5851163.html1 教科書里的單例模式我們都很清楚一個簡單的單例模式該怎樣去實現&#xff1a;構造函數聲明為private或protect防止被外部函數實例化&#xff0c;內部保存一個private static的類指針保存唯一的實例&#xff0c;實例的…
閱讀更多...
計算矩陣的逆和行列式的值(高斯消元+LU分解)

計算矩陣的逆和行列式的值(高斯消元+LU分解)

計算矩陣的逆 選主元的高斯消元法 樸素的高斯消元法是將矩陣A和單位矩陣放在一起&#xff0c;通過行操作&#xff08;或者列操作&#xff09;將A變為單位矩陣&#xff0c;這個時候單位矩陣就是矩陣A的逆矩陣。從上到下將A變為上三角矩陣的復雜度為O(n3n^3n3)&#xff0c;再從下…
閱讀更多...
Linux網絡編程——tcp并發服務器（epoll實現）

Linux網絡編程——tcp并發服務器（epoll實現）

https://blog.csdn.net/lianghe_work/article/details/46551871通過epoll實現tcp并發回執服務器&#xff08;客戶端給服務器發啥&#xff0c;服務器就給客戶端回啥&#xff09; 代碼如下&#xff1a;#include <string.h>#include <stdio.h>#include <stdlib.h&g…
閱讀更多...
證明AVL樹的上界和下界

證明AVL樹的上界和下界

對于n個節點的AVL樹&#xff0c;其高度最低的時候肯定為葉子節點只在最后一層和倒數第二層的時候。即對于2k?1<n≦2k1?12^k-1< n\leqq 2^{k1}-12k?1<n≦2k1?1的時候下界都為kkk。因此下界為h┌log2(n1)┐?1h\ulcorner log_2(n1)\urcorner-1h┌log2?(n1)┐?1 對…
閱讀更多...
淺談dup和dup2的用法

淺談dup和dup2的用法

https://blog.csdn.net/u012058778/article/details/78705536一、dup和dup2函數 這兩個函數都可以來復制一個現有的文件描述符&#xff0c;他們的聲明如下&#xff1a;#include <unistd.h>int dup(int fd);int dup2(int fd, int fd 2); 123 關于dup函數&#xff0c;當我…
閱讀更多...
C++ cin 實現循環讀入

C++ cin 實現循環讀入

習慣了使用while(~scanf("%d",x)){}來實現循環讀入&#xff0c;但是有時候使用泛型編程的時候就必須使用C中的cin&#xff0c;但是當我想要實現循環讀入的時候卻發現有些困難。 我們可以看一下下面這個簡單的例子&#xff1a; #include <iostream>using name…
閱讀更多...
BFPTR算法詳解+實現+復雜度證明

BFPTR算法詳解+實現+復雜度證明

BFPTR算法是由Blum、Floyed、Pratt、Tarjan、Rivest這五位牛人一起提出來的&#xff0c;其特點在于可以以最壞復雜度為O(n)O(n)O(n)地求解top?ktop-ktop?k問題。所謂top?ktop-ktop?k問題就是從一個序列中求解其第k大的問題。 top?ktop-ktop?k問題有許多解決方法&#xff…
閱讀更多...
C++子類對象隱藏了父類的同名成員函數（隱藏篇）

C++子類對象隱藏了父類的同名成員函數（隱藏篇）

https://blog.csdn.net/alpha_love/article/details/75222175#include <iostream>#include <stdlib.h>#include <string>using namespace std;/*** 定義人類: Person* 數據成員: m_strName* 成員函數: attack()*/class Person{public:Person(){cout<<&…
閱讀更多...
隨機化快速排序+快速選擇 復雜度證明+運行測試

隨機化快速排序+快速選擇 復雜度證明+運行測試

對于快速排序和快速選擇我之前的文章已經有詳細的說明&#xff0c;需要了解的同學可以移步 傳送門&#xff1a;快速排序&#xff5c;快速選擇(BFPTR) 所謂隨機化其實就是選擇樞紐的時候使用隨機數選擇而已&#xff0c;實現起來很簡單。但是我們使用隨機數如何保證復雜度呢&am…
閱讀更多...
C++子類父類成員函數的覆蓋和隱藏實例詳解

C++子類父類成員函數的覆蓋和隱藏實例詳解

https://www.jb51.net/article/117380.htm函數的覆蓋覆蓋發生的條件&#xff1a; &#xff08;1&#xff09; 基類必須是虛函數&#xff08;使用virtual 關鍵字來進行聲明&#xff09; &#xff08;2&#xff09;發生覆蓋的兩個函數分別位于派生類和基類 &#xff08;3&#xf…
閱讀更多...
【Linux基礎】Linux的5種IO模型詳解

【Linux基礎】Linux的5種IO模型詳解

引入 為了更好的理解5種IO模型的區別&#xff0c;在介紹IO模型之前&#xff0c;我先介紹幾個概念 1.進程的切換 &#xff08;1&#xff09;定義 為了控制進程的執行&#xff0c;內核必須有能力掛起正在CPU上運行的進程&#xff0c;并恢復以前掛起的某個進程的執行。即從用戶…
閱讀更多...
計算機網絡【五】廣播通信+以太網

計算機網絡【五】廣播通信+以太網

局域網的拓撲 廣域網使用點到點通信 局域網使用廣播通信 可以隨意向網絡中添加設備。 總線網星形網&#xff0c;使用集線器。現在多使用星形網絡。環狀網樹形網 其中匹配電阻用來吸收總線上傳播的信號。 共享通信媒體 靜態劃分信道 頻分復用、時分復用、波分復用、碼分復用…
閱讀更多...
聊聊Linux 五種IO模型

聊聊Linux 五種IO模型

一篇《聊聊同步、異步、阻塞與非阻塞》已經通俗的講解了&#xff0c;要理解同步、異步、阻塞與非阻塞重要的兩個概念點了&#xff0c;沒有看過的&#xff0c;建議先看這篇博文理解這兩個概念點。在認知上&#xff0c;建立統一的模型。這樣&#xff0c;大家在繼續看本篇時&#…
閱讀更多...
操作系統【四】分頁存儲管理

操作系統【四】分頁存儲管理

連續分配方式的缺點&#xff1a; 固定分區分配&#xff1a;缺乏靈活性&#xff0c;產生大量的內部碎片&#xff0c;內存的利用率較低 動態分區分配&#xff1a;會產生許多外部碎片&#xff0c;雖然可以用緊湊技術處理&#xff0c;但是緊湊技術的時間代價較高 基本分頁存儲管理…
閱讀更多...
聊聊同步、異步、阻塞與非阻塞

聊聊同步、異步、阻塞與非阻塞

近來遇到了一些常見的概念&#xff0c;尤其是網絡編程方面的概念&#xff0c;如&#xff1a;阻塞、非阻塞、異步I/O等等&#xff0c;對于這些概念自己也沒有太清晰的認識&#xff0c;只是很模糊的概念&#xff0c;說了解吧也了解&#xff0c;但是要讓自己準確的描述概念方面的具…
閱讀更多...
操作系統【五】分段內存管理+段頁式內存管理

操作系統【五】分段內存管理+段頁式內存管理

基本分段存儲管理 與分頁最大的區別&#xff1a;離散分配時所分配地址空間的基本單位不同 進程的地址空間&#xff1a;按照程序自身的邏輯關系劃分為若干個段&#xff0c;每個段都有一個段名&#xff0c;每段從0開始編址 內存分配規則&#xff1a;以段位單位進行分配&#xff…
閱讀更多...
計算機網絡【六】網絡層協議

計算機網絡【六】網絡層協議

網絡層負責在不同網絡之間盡力轉發數據包&#xff08;基于數據包的IP地址轉發&#xff09;。不負責丟失重傳&#xff0c;也不負責順序&#xff08;每一個數據包都是單獨選擇路徑&#xff09;。 可靠傳輸是由傳輸層實現。 網絡設備和OSI參考模型 通過分層&#xff0c;屏蔽了…
閱讀更多...
epoll 水平觸發與邊緣觸發

epoll 水平觸發與邊緣觸發

https://blog.csdn.net/lihao21/article/details/67631516?refmyread epoll也是實現I/O多路復用的一種方法&#xff0c;為了深入了解epoll的原理&#xff0c;我們先來看下epoll水平觸發&#xff08;level trigger&#xff0c;LT&#xff0c;LT為epoll的默認工作模式&#xff…
閱讀更多...
計算機網絡【3】網絡層

計算機網絡【3】網絡層

主要任務時把分組從源端發送到目的端&#xff0c;為分組交換網上的不同主機提供服務。網絡層傳輸單位是數據報 功能&#xff1a; 路由選擇與分組轉發&#xff08;最佳路徑 &#xff09;異構網絡互聯擁塞控制 數據交換方式 電路交換&#xff1a;通信時延小、有序傳輸、沒有沖…
閱讀更多...
C++空類的大小

C++空類的大小

https://blog.csdn.net/lihao21/article/details/47973609 本文中所說是C的空類是指這個類不帶任何數據&#xff0c;即類中沒有非靜態(non-static)數據成員變量&#xff0c;沒有虛函數(virtual function)&#xff0c;也沒有虛基類(virtual base class)。 直觀地看&#xff0c…
閱讀更多...
最新文章

Copyright @ 2022~2023