二分思想入門—快速排序

1-27更新：把幾個手殘的點改了下

冒泡排序，選擇排序能夠輕鬆解決桶排序浪費空間的問題，但在演算法的執行效率上卻犧牲了很多。由於冒泡排序與快速排序核心思想都是雙重嵌套循環，導致二者的時間複雜度達到了 。假設我們的計算機每秒次運算可以運行10億次，那麼對1億個數進行排序，桶排序只需要0.1秒，而冒泡排序則需要1千萬秒，將近115天之久！！！

那有沒有及不浪費空間又可以快一點的排序演算法呢？

那就是快速排序了。

假設我們對「6 1 2 7 9 3 4 5 10 8」這10個數進行排序，首先在這個排序中隨便找一個數作為基準數用來參照。為了方便，一般最左邊的數作為基準數，也就是這一個例子中的 6 。

接下來，我們的思路是先把所有比6小的數字放在在6的左邊，而比6大的數字放在6的右邊，類似於以下這種

3 1 2 5 4 6 9 7 10 8

接下來這組數字以6為基準，分成了左右兩部分：

3 1 2 5 4

9 7 10 8

我們重複第一步的思路，再分別設置基準數，重複上次的操作

1 2 3 5 4

7 8 9 10

這次操作後，這列數字被分的還剩下四組

1 2

5 4

7 8

10

再重複同樣的操作後，我們再把所有的數再組合在一起，由於基準數在數組中的位置不發生變化，會發現得到了我們想要的結果

1 2 3 4 5 6 7 8 9 10

這就是快速排序，也是二分最基本的思想。當然，具體的二分思想要比這高深的多，不在這裡做過多介紹，我們還是通過代碼先實現快速排序吧。

首先就是在數組首尾分別設置兩個起點

temp=a[left];//temp中存的就是基準數i=left;//left基準數，也是掃描的左起點 上文例子中的8j=right;//right是掃描的右起點 上文例子中的1

我們的目的是把比基準數小的數字全部放在其左邊，比基準數大的數字放在其右邊，所以從兩邊起點開始分別向從中間掃描，當從右向左掃描遇到比基準數小的數字時暫停掃描，從左往右掃描遇到比基準數大的數字時暫停掃描，交換兩數位置

6 [1] 2 7 9 3 4 5 10 [8] //開始掃描

6 1 2 [7] 9 3 4 [5] 10 8 //掃描暫停

6 1 2 [5] 9 3 4 [7] 10 8 //交換

交換之後，從交換點開始，繼續向中間掃描，直至兩個掃描點相遇

6 1 2 5 [9] 3 [4] 7 10 8 //再次交換

6 1 2 5 [4] 3 [9] 7 10 8 //再次交換

6 1 2 5 4 [3] 9 7 10 8 //掃描點相遇

掃描點相遇之後，基準數與相遇點的數字進行交換，基準數歸位，得到以下排列

3 1 2 5 4 6 9 7 10 8

這一段實現的code如下

while(i!=j) { //順序很重要，要從右往左找 while(a[j]>=temp && i<j) { j--; } //再從左往右找 while(a[i]<=temp && i<j) { i++; } //交換兩個數在數組中的位置 if(i<j)//當i與j沒有相遇 { t=a[i]; a[i]=a[j]; a[j]=t; } } //最終將基準線歸位 a[left]=a[i]; a[i]=temp;

完成以上步驟後，數列成功地分成了兩份，接著，對這兩段新的數組及它們裂生形成的新數組重複上面的操作，也就是遞歸，就可以得到我們想要的結果了，完整code如下

#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>using namespace std;int a[101],n;//定義全局變數，這兩個子變數需要在子函數中使用void quicksort(int left,int right){ int i,j,t,temp; if(left>right) { return; } temp=a[left];//temp中存的就是基準數 i=left; j=right; while(i!=j) { //順序很重要，要從右往左找 while(a[j]>=temp && i<j) { j--; } //再從左往右找 while(a[i]<=temp && i<j) { i++; } //交換兩個數在數組中的位置 if(i<j)//當i與j沒有相遇 { t=a[i]; a[i]=a[j]; a[j]=t; } } //最終將基準線歸位 a[left]=a[i]; a[i]=temp; quicksort(left,i-1); quicksort(i+1,right); return;}int main(){ int i,j; //讀入數據 cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; } quicksort(1,n);//調用二分排序 //輸出排序後的結果 for(i=1;i<=n;i++) { cout<<a[i]; } return 0;}

快速排序之所以比較快，是因為相比冒泡排序和選擇排序，每次交換都是跳躍式的。每次排序的時候，設置一個基準點，將小於等於基準點的數全部放到基準點的左邊，將大於等於基準點的數全部放在基準點的右邊。這樣，在每次交換的時候就不會像冒泡排序一樣只能在相鄰的數之間進行交換，交換的距離就大的多了。因此總的比較和交換次數就少了，速度自然就提高了。當然在最壞的情況下，仍可能時相鄰的兩個數進行交換。因此你快速排序的最差時間複雜度和冒泡排序，選擇排序一樣的，都是 ，但它的平均時間複雜度卻僅為 ，其效果還是非常可觀的。