本篇內(nèi)容主要講解“web中怎么寫一個快速排序的主體框架”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“web中怎么寫一個快速排序的主體框架”吧!

成都創(chuàng)新互聯(lián)歡迎來電：18982081108，為您提供成都網(wǎng)站建設(shè)網(wǎng)頁設(shè)計及定制高端網(wǎng)站建設(shè)服務(wù)，成都創(chuàng)新互聯(lián)網(wǎng)頁制作領(lǐng)域10年，包括成都社區(qū)文化墻等多個方面擁有多年的網(wǎng)站運(yùn)維經(jīng)驗，選擇成都創(chuàng)新互聯(lián)，為網(wǎng)站錦上添花。

1、首先需要設(shè)置一個樞軸元素即setPivot(int i)；

2、然后根據(jù)樞軸元素進(jìn)行劃分，將比樞軸元素大的排在右邊，小的排在左邊; 

3、分別對樞軸元素左邊和右邊的序列重復(fù)1和2的步驟進(jìn)行劃分，這是一個遞歸過程，整個代碼框架很簡單：

public void sort(int from, int to) {
        if (from >= to) {
            return;
        }
        setPivot(from);
        int partitionPos = partition(from, to);
        sort(from, partitionPos - 1);
        sort(partitionPos + 1, to);
  }

  每個子序列返回的條件是from >= to，由于樞軸元素是隨機(jī)選擇的，所以有以下幾種劃分情況：

1、軸樞元素正好能將序列分成均勻的兩半，如果是奇數(shù)個元素那么子序列退出的條件是from==to，如果是偶數(shù)個元素如2個，那么會出現(xiàn)from>to的情況。

2、軸樞元素不能將序列分成均勻的兩半，最極端的情況是軸樞元素將劃分的序列總是比它大或者小，此時同樣會出現(xiàn)from>to的情況。

實際上不管軸樞元素是否能將序列分成均勻的兩半，只要序列的個數(shù)是偶數(shù)個一定會出現(xiàn)from>to的情況！

目前只描述了最終劃分結(jié)果可能出現(xiàn)的情況，還沒有說明如何劃分，下面給出一個劃分的方案：

    假設(shè)給定序列7、6、5、4、3、2、1，并選擇4為樞軸，則示例代碼如下：

int   partition(int from, int to) {   
        int right = to;
        int left = from;
        while (true) {
            while (comparePivot(right) > 0) {
                right--;
            }

            while (comparePivot(left) < 0) {
                left++;
            }
            if (left == right) {
                break;
            }
            swap(left, right);
        }

        return left;
    }

     驗證一下：7和1進(jìn)行交換，序列變成1、6、5、4、3、2、7；left=0;right=6;

                      6和2進(jìn)行交換，序列變成1、2、5、4、3、6、7；left=1;right=5;

                      5和3進(jìn)行交換，序列變成1、2、3、4、5、6、7；left=2;right=4;

                      left=3;right=3;退出循環(huán)

                      然后分別調(diào)用sort(0,2),sort(4,6)，對于sort(0,2)的排序過程如下：

                       假設(shè)選取2為樞軸，由于原始序列已經(jīng)有序，right=1;left=1;退出循環(huán)。 最后的兩個遞歸是sort(0,0)以及sort(2,2),這兩個遞歸會由于from==to條件直接退出。

                      sort(4,6)也是類似的情況。

到此，相信大家對“web中怎么寫一個快速排序的主體框架”有了更深的了解，不妨來實際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！

網(wǎng)頁題目：web中怎么寫一個快速排序的主體框架
分享URL：http://www.rwnh.cn/article4/ghcgoe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供軟件開發(fā)、手機(jī)網(wǎng)站建設(shè)、App開發(fā)、ChatGPT、網(wǎng)站設(shè)計公司、云服務(wù)器

廣告

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