快速排序 C/C++

簡介：

我們日常學習中排序有最簡單的冒泡排序，雖然很方便就可以寫出來，但是時間復雜度太大 對于一些題來說很容易超時；所以便可以用快速排序
快排例題鏈接；

快速排序（Quicksort）：

既然稱之為快速排序 那么他就是排序演算法里最快的一個演算法；時間復雜度為O(NlogN)（平均運行時間），最壞的情況和冒泡排序的時間復雜度一樣為O(N^2)，
Quicksort 對冒泡排序演算法的一種改進，快速排序由C. A. R. Hoare在1960年提出，它的基本思想是：通過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然后再按此方法對這兩部分資料分別進行快速排序，整個排序程序可以遞回進行，以此達到整個資料變成有序序列，

話不多說 開始正題！！

快排思路：

1，任意從陣列里取一個數定為基準數（不要想太多 就是拿一個數作為參照系 進行對比）；
2，磁區，將比這個基準數大的數全放到它的右邊，小于或等于它的數全放到它的左邊；
3，分而治之，重復1，2步驟，直到整個資料變成有序序列；

知道了思路那我們就開始吧！！沖啊！！！！！

邏輯程序：

**1，**如一個這樣的陣列 num[n]；要對他進行排序；

num[0]=18;num[1]=20;num[3]=27num[4]=41;num[5]=5;num[6]=33;num[7]=15num[8]=17;

定義兩個變數 起始位置為st 末尾為en；

**2，**取第一個數為基準位， 那么第一個位置就空了 也就是0號下標的位置 然后進行比較；

基準位 op=num[0]；
num[0]空了 然后從右往左找找到比18小的數 放到 0號位置；

**3,**開始查找~~~~
8號的 17 比“op”也就是基準位的數(18)小 就放到空的位置(0號位置)
num[0]=num[8]；

4.
8號位置為空：
在從1號位置往右找比 “op”基準位數（后面簡稱基準） 大的數；20比 基準位數“op“（18）大 ； 把20放到空的位置（8號）；
num[8]=num[1]；

5,
1號位置為空：
從七號位置往左找比基準小的數 15小于基準（18） 把15放到空的位置（1號）；
num[1]=num[7];

6，
7號位置為空：
從2號位置往右找比基準（18）大的數； 27（2號）大于基準（18）； 把27放到空的位置（7號）；
num[7]=num[2];

8，
2號位置為空：
從6號位置往左找比基準（18）小的數； 5（5號）小于基準（18）；把5放到空的位置（2號）；
num[2]=num[5];

9，
5號位置為空：
從3號位置往右找比基準（18）大的數； 19（3號）大于基準（18）;把19放到空的位置（5號）；
Num[5]=num[3];

10，
3號位置為空：
那么就剩一個4號位置了 從4號開始找一直到5號 發現沒有比基準小的數了
回圈結束；

最后把基準（18）填到最后一個空里（3號）：

num[3]=op(基準)；

11.
我們發現 經過一輪排序后 基準左邊的數都比基準（18）小 基準右邊的數都比基準（18）大！！
這時磁區就完成了！！

12， 分開的每一個區都進行上述邏輯直到整個資料變成有序序列！！

接下來就是快排的第三個思想： 分而治之！！；
呼叫原函式繼續磁區 然后再治！直到整個資料變成有序序列！！*****

	quick(num,st,i-1); //左邊的所有值在呼叫此函式進行排序
    quick(num,i+1,en); //右的所有值在呼叫此函式進行排序

沒學程式語言也能看懂的代碼（注釋超多！）

###說那么多沒用 再來一段保姆式代碼！！！###

#include <iostream>

using namespace std; int num[1000]; void quick(int num[],int st,int en) {
    if(st>=en)//左端點大于右端點 排序結束
        return ;
    int i=st; //左右端點賦值給 i j 進行分治
    int j=en;
    int op=num[i];   //確定基準位；基準位這時便空了  方便于下面 @注釋1找到的值填到這個位置；
                 // 確定第一個位基準位比較好理解 看個人喜好哪個都可以為基準的

    while(i<j) //一切都是左端點大于右端點下進行
    {
        while(i<j&&num[j]>=op)  //從右往左查找到比基準位小的數然后結束回圈         @注釋1
            j--;                 //同時  j--  一個一個查 不滿足回圈條件 結束回圈  得到的 j 的值為比基準位小的數的下標
        num[i]=num[j];            // 把找到的數填到空的那個位置 同時下標為 j 的位置就空了方便于 @注釋3的值填入  @注釋2
        while(i<j&&num[i]<=op)	//從左往右查找到比基準位 大 的數然后結束回圈
            i++ ;             // i++ 不滿足回圈條件 回圈結束退出得到比基準位小的數的下標
        num[j]=num[i]; 		 // 把找到的數填到 @注釋2 得到的空位置  @注釋3
    }					//然后回圈進行 把比基準位的大的值都放在了左邊 小的放在了右邊；

    num[i]=op;  //把基準位的值填到回圈后剩下的那個空位；
                                             // 都看到這兒了 還不三連！！？？？？
    //分治 左邊和右邊在進行如上排序
    quick(num,st,i-1); //左邊的所有值在呼叫此函式進行排序
    quick(num,i+1,en); //右的所有值在呼叫此函式進行排序


} int main() {
    int n;
    cin>>n;  //n代表有幾個數
    for(int a=0; a<n; a++)
        cin>>num[a];//輸入n個數；
    quick(num,0,n-1);//呼叫快排函式；
    for(int a=0; a<n; a++)
        cout<<num[a]<<" ";//輸出結果；
    cout<<endl;
    return 0； }

~注釋可能有點多 但為了讓你懂我真的煞費苦心！！QAQ
那再來一段沒有注釋的！；

沒有注釋的快排代碼~

#include <iostream>

using namespace std;
int num[1000];
void quick(int num[],int st,int en)
{
    if(st>=en)
        return ;
    int i=st;
    int j=en;
    int op=num[i];
   while(i<j)
        {while(i<j&&num[j]>=op)
            j--;
        num[i]=num[j];
        while(i<j&&num[i]<=op)
            i++;
        num[j]=num[i];
    }

    num[i]=op;

    quick(num,st,i-1);
    quick(num,i+1,en);


}
int main()
{
    int n;
    cin>>n;
    for(int a=0; a<n; a++)
        cin>>num[a];
    quick(num,0,n-1);
    for(int a=0; a<n; a++)
        cout<<num[a]<<" ";
    cout<<endl;
    return 0;
}

編譯結果：

看到這里那說明你已經學會了 如果還是有不懂的地方可以私信我哦~~
歡迎各位網友指點 一起學習！！！！！
爆肝之作 實屬不易 給個贊唄~ 謝謝各位兄弟姐妹！！