算法09：快速排序——分治法Part5

（5）快速排序

快速排序是對冒泡排序的一種改進，基本思想是：通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列。

例如将數組R={6, 8, 7, 9, 0,1, 2, 3, 4, 5}從小到大排序

（1）在數組中任取一個數作為基準數，可以随機取，或者取中間的數，一般是取每次遞歸的第一個元素，該數組中取temp=R[0] =6,i=1,j=9

（2）以temp 為基準将數組中的數劃分為兩部分，左邊比temp都小，右邊比temp都大，具體過程如下

           a.從右邊，即j=9開始，找到第一個比temp小的數，R中為R[9]=5,與R[i]=R[0]交換， 交換後順序為{5, 8, 7, 9,   0,1, 2, 3, 4, &}（&暫時空缺）

           b.a中找出一個數以後從左邊，即i=1(i=0可以跳過)開始，找到第一個比temp大的數，R中為R[1]=8,與R[j]=R[9] 交換,交換後順序為{5, &, 7, 9, 0,1, 2, 3, 4, 8}（&暫時空缺）

          c.再從右邊開始找，一直到i>=j時結束

（3）一趟快速排序過程如下圖

一趟排序以後數組分為（5,4,2,3,0,1）(9,7,8)兩部分，再分别對這兩個數組遞歸排序

完整程式

#include <cstdlib>
#include <iostream>

using namespace std;

int Partition(int R[], int l, int r)
{
    int i = l, j = r+1, temp = R[l];
    
    while(i < j){
        //從右開始找到第一個小于temp的數 
          while(i < j && R[--j] > temp);
          R[i] = R[j];
        //從左開始找到第一個大于temp的數  
          while(i < j && R[++i] < temp);
          R[j] = R[i];
    }
    
    R[j] = temp;
    
    return j;
} 

void QuickSort(int R[], int l, int r)
{
     if(l<r){
        int p = Partition(R,l,r);
        //對左區間排序 
        QuickSort(R,l,p-1);
        //對右區間排序 
        QuickSort(R,p+1,r);
     }
}

int main()
{
    int R[] = {6, 8, 7, 9, 0,
            1, 2, 3, 4, 5};
    int n = 10;
    
    QuickSort(R, 0, n-1); 
    
    for(int i = 0; i  < n; i++){
            cout<<R[i]<<" ";
    }
    cout<<endl;
    
    system("PAUSE");
    return 0;
}