国产美女av经典,91精品区一区,日韩av国产探花电影

本文轉(zhuǎn)載至：https://blog.csdn.net/insistGoGo/article/details/7785038
1、快速排序的基本思想：

快速排序使用分治的思想，通過一趟排序?qū)⒋判蛄蟹指畛蓛刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小。之后分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序的目的。

2、快速排序的三個(gè)步驟：

(1)選擇基準(zhǔn)：在待排序列中，按照某種方式挑出一個(gè)元素，作為 "基準(zhǔn)"（pivot）

(2)分割操作：以該基準(zhǔn)在序列中的實(shí)際位置，把序列分成兩個(gè)子序列。此時(shí)，在基準(zhǔn)左邊的元素都比該基準(zhǔn)小，在基準(zhǔn)右邊的元素都比基準(zhǔn)大

(3)遞歸地對(duì)兩個(gè)序列進(jìn)行快速排序，直到序列為空或者只有一個(gè)元素。

3、選擇基準(zhǔn)的方式

對(duì)于分治算法，當(dāng)每次劃分時(shí)，算法若都能分成兩個(gè)等長(zhǎng)的子序列時(shí)，那么分治算法效率會(huì)達(dá)到最大。也就是說，基準(zhǔn)的選擇是很重要的。選擇基準(zhǔn)的方式?jīng)Q定了兩個(gè)分割后兩個(gè)子序列的長(zhǎng)度，進(jìn)而對(duì)整個(gè)算法的效率產(chǎn)生決定性影響。

最理想的方法是，選擇的基準(zhǔn)恰好能把待排序序列分成兩個(gè)等長(zhǎng)的子序列

我們介紹三種選擇基準(zhǔn)的方法

方法(1)：固定位置

思想：取序列的第一個(gè)或最后一個(gè)元素作為基準(zhǔn)

基本的快速排序

int SelectPivot(int arr[],int low,int high) {
    return arr[low];//選擇選取序列的第一個(gè)元素作為基準(zhǔn)
}

注意：基本的快速排序選取第一個(gè)或最后一個(gè)元素作為基準(zhǔn)。但是，這是一直很不好的處理方法。

測(cè)試數(shù)據(jù)：

1343482840_6721.jpg

測(cè)試數(shù)據(jù)分析：如果輸入序列是隨機(jī)的，處理時(shí)間可以接受的。如果數(shù)組已經(jīng)有序時(shí)，此時(shí)的分割就是一個(gè)非常不好的分割。因?yàn)槊看蝿澐种荒苁勾判蛐蛄袦p一，此時(shí)為最壞情況，快速排序淪為起泡排序，時(shí)間復(fù)雜度為Θ(n^2)。而且，輸入的數(shù)據(jù)是有序或部分有序的情況是相當(dāng)常見的。因此，使用第一個(gè)元素作為樞紐元是非常糟糕的，為了避免這個(gè)情況，就引入了下面兩個(gè)獲取基準(zhǔn)的方法。

方法(2)：隨機(jī)選取基準(zhǔn)

引入的原因：在待排序列是部分有序時(shí)，固定選取樞軸使快排效率底下，要緩解這種情況，就引入了隨機(jī)選取樞軸

思想：取待排序列中任意一個(gè)元素作為基準(zhǔn)

隨機(jī)化算法

/*隨機(jī)選擇樞軸的位置，區(qū)間在low和high之間*/
int SelectPivotRandom(int arr[],int low,int high) {
    //產(chǎn)生樞軸的位置
    srand((unsigned)time(NULL));
    int pivotPos = rand()%(high - low) + low;
    //把樞軸位置的元素和low位置元素互換，此時(shí)可以和普通的快排一樣調(diào)用劃分函數(shù)
    swap(arr[pivotPos],arr[low]);
    return arr[low];
}

測(cè)試數(shù)據(jù)：

1343483154_7918.jpg

測(cè)試數(shù)據(jù)分析：:這是一種相對(duì)安全的策略。由于樞軸的位置是隨機(jī)的，那么產(chǎn)生的分割也不會(huì)總是會(huì)出現(xiàn)劣質(zhì)的分割。在整個(gè)數(shù)組數(shù)字全相等時(shí)，仍然是最壞情況，時(shí)間復(fù)雜度是O(n^{2）。實(shí)際上，隨機(jī)化快速排序得到理論最壞情況的可能性僅為1/(2}n）。所以隨機(jī)化快速排序可以對(duì)于絕大多數(shù)輸入數(shù)據(jù)達(dá)到O(nlogn）的期望時(shí)間復(fù)雜度。一位前輩做出了一個(gè)精辟的總結(jié)：“隨機(jī)化快速排序可以滿足一個(gè)人一輩子的人品需求?！?/p>

方法(3)：三數(shù)取中（median-of-three）

引入的原因：雖然隨機(jī)選取樞軸時(shí)，減少出現(xiàn)不好分割的幾率，但是還是最壞情況下還是O(n^2），要緩解這種情況，就引入了三數(shù)取中選取樞軸

分析：最佳的劃分是將待排序的序列分成等長(zhǎng)的子序列，最佳的狀態(tài)我們可以使用序列的中間的值，也就是第N/2個(gè)數(shù)?？墒牵@很難算出來，并且會(huì)明顯減慢快速排序的速度。這樣的中值的估計(jì)可以通過隨機(jī)選取三個(gè)元素并用它們的中值作為樞紐元而得到。事實(shí)上，隨機(jī)性并沒有多大的幫助，因此一般的做法是使用左端、右端和中心位置上的三個(gè)元素的中值作為樞紐元。顯然使用三數(shù)中值分割法消除了預(yù)排序輸入的不好情形，并且減少快排大約14%的比較次數(shù)

舉例：待排序序列為：8 1 4 9 6 3 5 2 7 0

左邊為：8，右邊為0，中間為6.

我們這里取三個(gè)數(shù)排序后，中間那個(gè)數(shù)作為樞軸，則樞軸為6

注意：在選取中軸值時(shí)，可以從由左中右三個(gè)中選取擴(kuò)大到五個(gè)元素中或者更多元素中選取，一般的，會(huì)有（2t＋1）平均分區(qū)法（median-of-(2t+1)，三平均分區(qū)法英文為median-of-three）。

具體思想：對(duì)待排序序列中l(wèi)ow、mid、high三個(gè)位置上數(shù)據(jù)進(jìn)行排序，取他們中間的那個(gè)數(shù)據(jù)作為樞軸，并用0下標(biāo)元素存儲(chǔ)樞軸。

即：采用三數(shù)取中，并用0下標(biāo)元素存儲(chǔ)樞軸。

/*函數(shù)作用：取待排序序列中l(wèi)ow、mid、high三個(gè)位置上數(shù)據(jù)，選取他們中間的那個(gè)數(shù)據(jù)作為樞軸*/
 int SelectPivotMedianOfThree(int arr[],int low,int high) {
    int mid = low + ((high - low) >> 1);//計(jì)算數(shù)組中間的元素的下標(biāo)
    //使用三數(shù)取中法選擇樞軸
    if (arr[mid] > arr[high]) {//目標(biāo): arr[mid] <= arr[high]
        swap(arr[mid],arr[high]);
    }
    if (arr[low] > arr[high]) {//目標(biāo): arr[low] <= arr[high]
        swap(arr[low],arr[high]);
    }
    if (arr[mid] > arr[low]) {//目標(biāo): arr[low] >= arr[mid]
        swap(arr[mid],arr[low]);
    }
    //此時(shí)，arr[mid] <= arr[low] <= arr[high]
    return arr[low];
    //low的位置上保存這三個(gè)位置中間的值
    //分割時(shí)可以直接使用low位置的元素作為樞軸，而不用改變分割函數(shù)了
}

測(cè)試數(shù)據(jù)：

1343483297_2415.jpg

測(cè)試數(shù)據(jù)分析：使用三數(shù)取中選擇樞軸優(yōu)勢(shì)還是很明顯的，但是還是處理不了重復(fù)數(shù)組

優(yōu)化1、當(dāng)待排序序列的長(zhǎng)度分割到一定大小后，使用插入排序。

原因：對(duì)于很小和部分有序的數(shù)組，快排不如插排好。當(dāng)待排序序列的長(zhǎng)度分割到一定大小后，繼續(xù)分割的效率比插入排序要差，此時(shí)可以使用插排而不是快排

截止范圍：待排序序列長(zhǎng)度N = 10，雖然在5~20之間任一截止范圍都有可能產(chǎn)生類似的結(jié)果，這種做法也避免了一些有害的退化情形。摘自《數(shù)據(jù)結(jié)構(gòu)與算法分析》Mark Allen Weiness 著

if (high - low + 1 < 10) {
    InsertSort(arr,low,high);
    return;
}//else時(shí)，正常執(zhí)行快排

測(cè)試數(shù)據(jù)：

1343483399_3096.jpg

測(cè)試數(shù)據(jù)分析：針對(duì)隨機(jī)數(shù)組，使用三數(shù)取中選擇樞軸+插排，效率還是可以提高一點(diǎn)，真是針對(duì)已排序的數(shù)組，是沒有任何用處的。因?yàn)榇判蛐蛄惺且呀?jīng)有序的，那么每次劃分只能使待排序序列減一。此時(shí)，插排是發(fā)揮不了作用的。所以這里看不到時(shí)間的減少。另外，三數(shù)取中選擇樞軸+插排還是不能處理重復(fù)數(shù)組

優(yōu)化2、在一次分割結(jié)束后，可以把與Key相等的元素聚在一起，繼續(xù)下次分割時(shí)，不用再對(duì)與key相等元素分割

舉例：

待排序序列 1 4 6 7 6 6 7 6 8 6

三數(shù)取中選取樞軸：下標(biāo)為4的數(shù)6

轉(zhuǎn)換后，待分割序列：6 4 6 7 1 6 7 6 8 6

? 樞軸key：6

本次劃分后，未對(duì)與key元素相等處理的結(jié)果：1 4 6 6 7 6 7 6 8 6

下次的兩個(gè)子序列為：1 4 6 和 7 6 7 6 8 6

本次劃分后，對(duì)與key元素相等處理的結(jié)果：1 4 6 6 6 6 6 7 8 7

下次的兩個(gè)子序列為：1 4 和 7 8 7

經(jīng)過對(duì)比，我們可以看出，在一次劃分后，把與key相等的元素聚在一起，能減少迭代次數(shù)，效率會(huì)提高不少

具體過程：在處理過程中，會(huì)有兩個(gè)步驟

第一步，在劃分過程中，把與key相等元素放入數(shù)組的兩端

第二步，劃分結(jié)束后，把與key相等的元素移到樞軸周圍

舉例：

待排序序列 1 4 6 7 6 6 7 6 8 6

三數(shù)取中選取樞軸：下標(biāo)為4的數(shù)6

轉(zhuǎn)換后，待分割序列：6 4 6 7 1 6 7 6 8 6

? 樞軸key：6

第一步，在劃分過程中，把與key相等元素放入數(shù)組的兩端

結(jié)果為：6 4 1 6(樞軸) 7 8 7 6 6 6

此時(shí)，與6相等的元素全放入在兩端了

第二步，劃分結(jié)束后，把與key相等的元素移到樞軸周圍

結(jié)果為：1 4 66(樞軸) 6 6 6 7 8 7

此時(shí)，與6相等的元素全移到樞軸周圍了

之后，在1 4 和 7 8 7兩個(gè)子序列進(jìn)行快排

代碼

void QSort(int arr[],int low,int high) {
    int first = low;
    int last = high;
    int left = low;
    int right = high;
    int leftLen = 0;
    int rightLen = 0;
    if (high - low + 1 < 10) {
        InsertSort(arr,low,high);
        return;
    }
    //一次分割
    int key = SelectPivotMedianOfThree(arr,low,high);//使用三數(shù)取中法選擇樞軸
    while(low < high) {
        while(high > low && arr[high] >= key) {
            if (arr[high] == key) {//處理相等元素
                swap(arr[right],arr[high]);
                right--;
                rightLen++;
            }
            high--;
        }
        arr[low] = arr[high];
        while(high > low && arr[low] <= key) {
            if (arr[low] == key){
                swap(arr[left],arr[low]);
                left++;
                leftLen++;
            }
            low++;
        }
        arr[high] = arr[low];
    }
    arr[low] = key;
    //一次快排結(jié)束
    //把與樞軸key相同的元素移到樞軸最終位置周圍
    int i = low - 1;
    int j = first;
    while(j < left && arr[i] != key) {
        swap(arr[i],arr[j]);
        i--;
        j++;
    }
    i = low + 1;
    j = last;
    while(j > right && arr[i] != key) {
        swap(arr[i],arr[j]);
        i++;
        j--;
    }
    QSort(arr,first,low - 1 - leftLen);
    QSort(arr,low + 1 + rightLen,last);
}

測(cè)試數(shù)據(jù)：

1343483583_7922.jpg

測(cè)試數(shù)據(jù)分析：三數(shù)取中選擇樞軸+插排+聚集相等元素的組合，效果竟然好的出奇。

原因：在數(shù)組中，如果有相等的元素，那么就可以減少不少冗余的劃分。這點(diǎn)在重復(fù)數(shù)組中體現(xiàn)特別明顯啊。

其實(shí)這里，插排的作用還是不怎么大的。

優(yōu)化3：優(yōu)化遞歸操作

快排函數(shù)在函數(shù)尾部有兩次遞歸操作，我們可以對(duì)其使用尾遞歸優(yōu)化

優(yōu)點(diǎn)：如果待排序的序列劃分極端不平衡，遞歸的深度將趨近于n，而棧的大小是很有限的，每次遞歸調(diào)用都會(huì)耗費(fèi)一定的?？臻g，函數(shù)的參數(shù)越多，每次遞歸耗費(fèi)的空間也越多。優(yōu)化后，可以縮減堆棧深度，由原來的O(n)縮減為O(logn)，將會(huì)提高性能。

代碼：

void QSort(int arr[],int low,int high) { 
    int pivotPos = -1;
    if (high - low + 1 < 10) {
        InsertSort(arr,low,high);
        return;
    }
    while(low < high) {
        pivotPos = Partition(arr,low,high);
        QSort(arr,low,pivot-1);
        low = pivot + 1;
    }
}

注意：在第一次遞歸后，low就沒用了，此時(shí)第二次遞歸可以使用循環(huán)代替

測(cè)試數(shù)據(jù)：