【排序】快速排序C++實作總結

一、算法步驟

快速排序的基本思想是：

1．先從數列中取出一個數作為基準數。

2．分區過程，将比這個數大的數全放到它的右邊，小于或等于它的數全放到它的左邊。

3．再對左右區間重複第二步，直到各區間隻有一個數。

 算法步驟：

1）設定兩個變量i、j，排序開始的時候：i=0，j=N-1；

2）以第一個數組元素作為關鍵資料，指派給

key，即

key=A[0]；

3）從j開始向前搜尋，即由後開始向前搜尋(j--)，找到第一個小于

key的值A[j]，将A[j]賦給A[i]；

4）從i開始向後搜尋，即由前開始向後搜尋(i++)，找到第一個大于

key的A[i]，将A[i]賦給A[j]；

5）重複第3、4步，直到i=j；

二、運作過程圖示

雖然快速排序稱為分治法，但分治法這三個字顯然無法很好的概括快速排序的全部步驟。是以我的對快速排序作了進一步的說明：挖坑填數+分治法：

先來看執行個體吧，定義下面再給出（最好能用自己的話來總結定義，這樣對實作代碼會有幫助）。

以一個數組作為示例，取區間第一個數為基準數。

1	2	3	4	5	6	7	8	9
72	6	57	88	60	42	83	73	48	85

初始時，i = 0;  j = 9;   X = a[i] = 72

由于已經将a[0]中的數儲存到X中，可以了解成在數組a[0]上挖了個坑，可以将其它資料填充到這來。

從j開始向前找一個比X小或等于X的數。當j=8，符合條件，将a[8]挖出再填到上一個坑a[0]中。a[0]=a[8]; i++;  這樣一個坑a[0]就被搞定了，但又形成了一個新坑a[8]，這怎麼辦了？簡單，再找數字來填a[8]這個坑。這次從i開始向後找一個大于X的數，當i=3，符合條件，将a[3]挖出再填到上一個坑中a[8]=a[3]; j--;

數組變為：

1	2	3	4	5	6	7	8	9
48	6	57	88	60	42	83	73	88	85

 i = 3;   j = 7;   X=72

（注意：兩個88是因為a[8]=a[3]）

再重複上面的步驟，先從後向前找，再從前向後找。

從j開始向前找，當j=5，符合條件，将a[5]挖出填到上一個坑中，a[3] = a[5]; i++;

從i開始向後找，當i=5時，由于i==j退出。

此時，i = j = 5，而a[5]剛好又是上次挖的坑，是以将X填入a[5]。

數組變為：

1	2	3	4	5	6	7	8	9
48	6	57	42	60	72	83	73	88	85

可以看出a[5]前面的數字都小于它，a[5]後面的數字都大于它。是以再對a[0…4]和a[6…9]這二個子區間重複上述步驟就可以了。

三、實作方法

1.遞歸實作

方法1：

對挖坑填數進行總結

1．i =L; j = R; 将基準數挖出形成第一個坑a[i]。

2．j--由後向前找比它小的數，找到後挖出此數填前一個坑a[i]中。

int AdjustArray(int s[], int l, int r) //傳回調整後基準數的位置
{
       int i = l, j = r;
       int x = s[l]; //s[l]即s[i]就是第一個坑
       while (i < j)
       {
              // 從右向左找小于x的數來填s[i]
              while(i < j && s[j] >= x)
                     j--; 
              if(i < j)
              {
                     s[i] = s[j]; //将s[j]填到s[i]中，s[j]就形成了一個新的坑
                     i++;
              }
 
              // 從左向右找大于或等于x的數來填s[j]
              while(i < j && s[i] < x)
                     i++; 
              if(i < j)
              {
                     s[j] = s[i]; //将s[i]填到s[j]中，s[i]就形成了一個新的坑
                     j--;
              }
       }
       //退出時，i等于j。将x填到這個坑中。
       s[i] = x;
 
       return i;
}
 
再寫分治法的代碼：
void quick_sort1(int s[], int l, int r)
{
       if (l < r)
    {
              int i = AdjustArray(s, l, r);//先成挖坑填數法調整s[]
              quick_sort1(s, l, i - 1); // 遞歸調用
              quick_sort1(s, i + 1, r);
       }
}
這樣的代碼顯然不夠簡潔，對其組合整理下：
//快速排序
void quick_sort(int s[], int l, int r)
{
    if (l < r)
    {
              //Swap(s[l], s[(l + r) / 2]); //将中間的這個數和第一個數交換 參見注1
        int i = l, j = r, x = s[l];
        while (i < j)
        {
            while(i < j && s[j] >= x) // 從右向左找第一個小于x的數
                            j--; 
            if(i < j)
                            s[i++] = s[j];
                    
            while(i < j && s[i] < x) // 從左向右找第一個大于等于x的數
                            i++; 
            if(i < j)
                            s[j--] = s[i];
        }
        s[i] = x;
        quick_sort(s, l, i - 1); // 遞歸調用
        quick_sort(s, i + 1, r);
    }
}
int main(){
    int array[]={72,6,57,88,60,42,83,73,48,85};
    quick_sort(array,0,9);//或者quick_qort1()
    for(int i = 0 ; i <= 9 ; i++)
        cout<<array[i]<<" ";
    cout<<endl;
    return 0;
 }      

2.非遞歸（用棧模拟）      

#include<iostream>
#include<stack>
 
struct Num
{
    int low,high;
    Num(int low = 0, int high = 0)
    {
        this->low = low;
        this->high = high;
    }
};
void sort(int val[],int ,int );
int main(int argc, _TCHAR* argv[])
{
    int arg[5] = {90,70,18,30,520};
    sort(arg,0,4);
    for(int i = 0; i < 5; i++)
    {
        std::cout<<arg[i]<<" ";
    }
    system("pause");
    return 0;
}
 
 
void sort(int arr[], int begin, int end)
{
    std::stack<Num> myStack;
    myStack.push(Num(begin, end));
    while(!myStack.empty())
    {
        int i = myStack.top().low;
        int j = myStack.top().high;
        int b = i;
        int e = j;
        myStack.pop();
        if(i >= j)
            continue;
        int key = arr[i];
        while(i < j)
        {
            while(i < j && arr[j] >= key)
                j--;
            if(i < j)
                arr[i++] = arr[j];
            while(i < j && arr[i] <= key)
                i++;
            if(i < j)
                arr[j--] = arr[i];
        }
        arr[i] = key;
        myStack.push(Num(b, i - 1));
        myStack.push(Num(i + 1, e));
    }
}