一種遞歸實現的快速排序精講

簡介：

快速排序是個“綜合素質”較好的排序，比如javaSE中的Arrays.sort()實現原理，也是用的是快速排序思想。下面就看看一種快速排序的遞歸實現方式

要點：

1，分治思想，把問題劃分成可以與本問題處理方式相同的若干子問題，使用遞歸來解決。

   如排序問題，可以

    （1）把原數組A[p,q]（原問題）劃分成三個部分 ：較小部分A[p,m-1]  中間元素x=A[m]  較大部分A[m+1,q] 

          這樣把部分當做一個整體看待是有序的A[p,m-1] <  A[m]  <  A[m+1,q]

    （2）同理，無論是較小部分還是較大部分都可以繼續按（1）操作繼續劃分得更細，直到每個部分的元素

          被劃分得只有單個元素，原數組之間每個元素就有序了

特征：

1，快速排序是原址排序，子問題解決的時候，不需要整體再次合并排序結果

2，遞歸調用在非常的數據的時候可能會發生棧溢出（遞歸深度太大）

難點：

   如何劃分成相對有序的三個部分？

      思路：

         （1）在原數組的某個好識別的位置取出一個數做中間元素x（部分2）。（一般取數組末元素，如x=A[q]）

         （2）采取一個位置變量i來左劃分界線，保證i上和i的左邊都是小部分元素（部分1）。

            （i的初始位置應當在問題范圍的前一個位置，因為此時還沒開始劃分）

         （3）除了x元素，循環取出原數組中的每個元素A[j]與x做比較

             遇到不大于中間元素x要收集到界線上：

                 原界線i右移一個，此時i指向的元素是不確定性質的元素，

                 不確定元素和已經遇到的確定的小部分元素A[j]交換位置。（不確定換確定）

             遇到大于中間元素的，界線i不動，j繼續向右掃描（i和j之間的定是大部分元素,部分3）

         （4）讓中間元素交換到真正位置。一遍循環后，可以分出 小部分 和 大部分，

              此時只要在界線的右一個（即大部分中的某個元素）與中間元素交換即可讓劃分的三個部分滿足排序關系。

圖片描述：

代碼描述：

void quicklySort(int *arr , int start , int last){

    int mid;

    if(start<last){

        mid = partition(arr, start, last);//劃分子問題

        quicklySort(arr, start , mid-1);//解決左邊部分

        quicklySort(arr, mid+1, last);//解決右邊部分

    }

}

int partition(int *arr, int start, int last){

    int x = arr[last];//取本段數組最后一個元素，稍后使其成為劃分好的中間元素

    int i=0,j=0;

    i=start-1;//使用i來控制兩個部分的分界，初始值在子問題范圍的前一個

    for(j=start;j<= last-1; j++){

        if(arr[j]<= x){//如果j走過的值是屬于較小部分

           ++i;//較小部分分界線多收集一個空間

           swap(arr[i],arr[j]);//把屬于較小部分的值交換到這個空間（原址排序）

        }

        //如果是較大部分，讓j繼續向后滑行

    }

    swap(arr[i+1],arr[last]);//把選擇參照的值交換到小部分和大部分之間

    return i+1;//返回劃分好的中間位置

}