一種遞歸實現(xiàn)的快速排序精講-創(chuàng)新互聯(lián)

簡介：

創(chuàng)新互聯(lián)公司于2013年開始，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項目成都網(wǎng)站制作、成都網(wǎng)站設(shè)計、外貿(mào)營銷網(wǎng)站建設(shè)網(wǎng)站策劃，項目實施與項目整合能力。我們以讓每一個夢想脫穎而出為使命，1280元婺源做網(wǎng)站,已為上家服務(wù),為婺源各地企業(yè)和個人服務(wù),聯(lián)系電話:028-86922220

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

要點：

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

   如排序問題，可以

    （1）把原數(shù)組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）同理，無論是較小部分還是較大部分都可以繼續(xù)按（1）操作繼續(xù)劃分得更細，直到每個部分的元素

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

特征：

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

2，遞歸調(diào)用在非常的數(shù)據(jù)的時候可能會發(fā)生棧溢出（遞歸深度太大）

難點：

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

     思路：

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

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

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

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

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

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

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

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

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

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

圖片描述：

代碼描述：

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];//取本段數(shù)組最后一個元素，稍后使其成為劃分好的中間元素

   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繼續(xù)向后滑行

   }

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

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

}

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

分享名稱：一種遞歸實現(xiàn)的快速排序精講-創(chuàng)新互聯(lián)
URL分享：http://muchs.cn/article14/cdscde.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App設(shè)計、自適應(yīng)網(wǎng)站、微信小程序、響應(yīng)式網(wǎng)站、動態(tài)網(wǎng)站、網(wǎng)站設(shè)計公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)