web中怎么寫一個快速排序的主體框架

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

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

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

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

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，由于樞軸元素是隨機選擇的，所以有以下幾種劃分情況：

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進行交換，序列變成1、6、5、4、3、2、7；left=0;right=6;

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

                      5和3進行交換，序列變成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中怎么寫一個快速排序的主體框架”有了更深的了解，不妨來實際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學習！