柚子快報(bào)激活碼778899分享：【排序算法】數(shù)據(jù)結(jié)構(gòu)排序詳解

http://yzkb.51969.com/

前言： 今天我們將講解我們數(shù)據(jù)結(jié)構(gòu)初階的最后一部分知識(shí)的學(xué)習(xí)，也是最為“炸裂”的知識(shí)---------排序算法的講解！?。?！

目錄

1.排序的概念及其運(yùn)用1.1排序的概念1.2排序運(yùn)用

2.常見(jiàn)排序算法的實(shí)現(xiàn)2.1 插入排序2.1.1直接插入排序2.1.2希爾排序( 縮小增量排序 )

2.2 選擇排序2.2.1直接選擇排序2.2.2堆排序

2.3交換排序2.3.1冒泡排序2.3.2 快速排序(重點(diǎn)）

2.4 歸并排序2.5 計(jì)數(shù)排序

3.各種內(nèi)部排序算法比較及運(yùn)用3.1內(nèi)部排序算法的比較3.2內(nèi)部排序算法的運(yùn)用

4 選擇題講解

1.排序的概念及其運(yùn)用

1.1排序的概念

排序：所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來(lái)的操作。 穩(wěn)定性：假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過(guò)排序，這些記錄的相對(duì)次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。 內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。常見(jiàn)的內(nèi)部排序算法有：【插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、計(jì)數(shù)排序等】

外部排序：數(shù)據(jù)元素太多不能同時(shí)放在內(nèi)存中，根據(jù)排序過(guò)程的要求不能在內(nèi)外存之間移動(dòng)數(shù)據(jù)的排序。

1.2排序運(yùn)用

要說(shuō)起排序，在我們?nèi)粘Ｉ畹姆椒矫婷婵梢哉f(shuō)都能看到。就拿我們平時(shí)網(wǎng)上買(mǎi)東西舉例，當(dāng)我們挑選時(shí)我們總會(huì)按照個(gè)人的需求進(jìn)行排序分類，例如當(dāng)我們買(mǎi)電腦時(shí)，會(huì)看到下圖：

我們可以從很多的角度去選擇我們心儀的，可以根據(jù)價(jià)格，銷量等等，看榜單的排名一定層度上能反映出大眾都認(rèn)可的東西?。。?/p>

2.常見(jiàn)排序算法的實(shí)現(xiàn)

插入排序是一種非常直觀的排序算法。其基本思想就是將一個(gè)待排序的記錄按其關(guān)鍵字的大小插入前面以及排好序的子序列中，直到全部記錄插入完成。 由插入排序的思想可以引申出三個(gè)最重要的排序算法：【直接插入排序，折半插入排序和希爾排序】

2.1 插入排序

2.1.1直接插入排序

根據(jù)上面的插入排序思想，不難得出一種最簡(jiǎn)單也是最直觀的直接插入排序算法。假設(shè)在排序過(guò)程中，待排序表L【1…n】在某次排序過(guò)程中的某一時(shí)刻狀態(tài)如下：

要將元素L[i]插入已有序的子序列L[1…i-1],需要執(zhí)行以下操作： 1）查找出L[i] 在L[1…i-1]中的插入位置k。 2）將L[k…i-1]中的所有元素依次向后移動(dòng)一個(gè)位置。 3）將L[i] 賦值到L[k].

為了實(shí)現(xiàn)對(duì) L [1… n ]的排序，可以將 L (2)~ L ( n ）依次插入前面已排好序的子序列，初始 L [1]可以視為是一個(gè)已排好序的子序列。上述操作執(zhí)行 n -1次就能得到一個(gè)有序的表。插入排序在實(shí)現(xiàn)上通常采用就地排序（空間復(fù)雜度為 O (1))，因而在從后向前的比較過(guò)程中，需要反復(fù)把已排序元素逐步向后挪位，為新元素提供插入空間。

我們通過(guò)舉例來(lái)具體解釋一哈步奏。假定初始序列為14, 33, 27, 10, 35, 19, 42, 44

（1）第一步：將第一個(gè)元素 14 看作是一個(gè)有序的子序列 {14}，將剩余元素逐個(gè)插入到此序列的適當(dāng)位置：

（2）第二步： 將 33 插入到 {14} 中，由于 33 > 14，所以 33 應(yīng)該插入到 14 的后面，新的有序序列變?yōu)?{14,33}；

（3）第三步：將 27 插入到 {14, 33} 中，由于 27 < 33 同時(shí) 27 > 14，所以 27 應(yīng)該插入到 14 和 33 的中間，新的有序序列變?yōu)?{14, 27, 33}；

（4）第四步：將 10 插入到 {14, 27, 33} 中，經(jīng)過(guò)依次和 33、27、14 比較，最終斷定 10 應(yīng)該插入到 14之前，新的有序序列變?yōu)?{10, 14, 27, 33}；

（5）第五步：將 35 插入到 {10, 14, 27, 33} 中，由于 35 > 33，所以 35 應(yīng)該插入到 33之后，新的有序序列變?yōu)?{10, 14, 27, 33, 35}

（6）第六步： 將 19 插入到 {10, 14, 27, 33, 35} 中，經(jīng)過(guò)依次和 35、33、27、14 比較，最終斷定 19應(yīng)該插入到 14 和 27 之間，新的有序序列變?yōu)?{10, 14, 19, 27, 33, 35}；

（7）第七步：將 42 插入到 {10, 14, 19, 27, 33, 35} 中，由于 42 > 35，所以 42 應(yīng)插入到 35之后，新的有序序列變?yōu)?{10, 14, 19, 27, 33, 35, 42}；

（8）第八步： 將 44 插入到 {10, 14, 19, 27, 33, 35, 42} 中，由于 44 > 42，所以 44 應(yīng)插入到 42 之后，新的有序序列變?yōu)?{10, 14, 19, 27, 33, 35, 42, 44}。

經(jīng)過(guò)將各個(gè)待排序的元素插入到有序序列的適當(dāng)位置，最終得到的就是一個(gè)包含所有元素的有序序列。

接下來(lái)我們通過(guò)動(dòng)畫(huà)形象的演示：

解釋：

1.從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序； 2.取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描； 3.如果該元素（已排序）大于新元素，將該元素移到下一位置； 4.重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置； 5.將新元素插入到該位置后； 6.重復(fù)步驟2~5。

代碼如下：

void InsertSort(int* a, int n)

{

for (int i = 0; i < n-1; ++i)

{

int end = i;

int tmp = a[end + 1];

while (end >= 0)

{

if (tmp < a[end])

{

a[end + 1] = a[end];

--end;

}

else

{

break;

}

}

a[end + 1] = tmp;

}

}

性能分析：

直接插入排序算法的性能分析如下：

空間效率：僅使用了常數(shù)個(gè)輔助單元，因而空間復(fù)雜度為 O (1)。 時(shí)間效率：在排序過(guò)程中，向有序子表中逐個(gè)地插入元素的操作進(jìn)行了 n -1趟，每趟操作都分為比較關(guān)鍵字和移動(dòng)元素，而比較次數(shù)和移動(dòng)次數(shù)取決于待排序表的初始狀態(tài)

在最好情況下，表中元素已經(jīng)有序，此時(shí)每插入一個(gè)元素，都只需比較一次而不用移動(dòng)元素，因而時(shí)間復(fù)雜度為 O ( n )。

在最壞情況下，表中元素順序剛好與排序結(jié)果中的元素順序相反（逆序），總的比較次數(shù)達(dá)到最大,總的移動(dòng)次數(shù)也達(dá)到最大.

平均情況下，考慮待排序表中元素是隨機(jī)的，此時(shí)可以取上述最好與最壞情況的平均值作為平均情況下的時(shí)間復(fù)雜度，總的比較次數(shù)與總的移動(dòng)次數(shù)均約為N^2／4。

因此，直接插入排序算法的時(shí)間復(fù)雜度為 O（N^2）

穩(wěn)定性：由于每次插入元素時(shí)總是從后向前先比較再移動(dòng)，所以不會(huì)出現(xiàn)相同元素相對(duì)位置發(fā)生變化的情況，即直接插入排序是一個(gè)穩(wěn)定的排序方法。

適用性：直接插入排序算法適用于順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的線性表。為鏈?zhǔn)酱鎯?chǔ)時(shí)，可以從前往后查找指定元素的位置。

注意：大部分排序算法都僅適用于順序存儲(chǔ)的線性表

2.1.2希爾排序( 縮小增量排序 )

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。但希爾排序是非穩(wěn)定排序算法。

從前面的分析可知，直接插入排序算法的時(shí)間復(fù)雜度為O(n^2)，但若待排序序列為“正序”時(shí)，其時(shí)間復(fù)雜度可以提升為O(n)。由此可見(jiàn)它更適用于基本有序的排序表和數(shù)據(jù)量不大的排序表。希爾排序正是基于以上兩點(diǎn)分析對(duì)直接插入排序進(jìn)行改造得來(lái)的?。。?/p>

希爾排序法的基本思想是： 先選定一個(gè)整數(shù)，把待排序文件中所有記錄分成個(gè)組，所有距離為的記錄分在同一組內(nèi)，并對(duì)每一組內(nèi)的記錄進(jìn)行排序。然后，取，重復(fù)上述分組和排序的工作。當(dāng)?shù)竭_(dá)=1時(shí)，所有記錄在統(tǒng)一組內(nèi)排好序。

我們通過(guò)舉例來(lái)說(shuō)明次算法的結(jié)題思路： 算法步驟：

選擇一個(gè)增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列個(gè)數(shù) k，對(duì)序列進(jìn)行 k 趟排序；

每趟排序，根據(jù)對(duì)應(yīng)的增量 ti，將待排序列分割成若干長(zhǎng)度為 m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為 1 時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。

動(dòng)畫(huà)展示：

代碼如下：

void ShellSort(int* a, int n)

{

// gap > 1 預(yù)排序

// gap == 1 直接插入排序

int gap = n;

while (gap > 1)

{

// gap = gap / 2;

// gap = gap / 3; // 9 8 不能保證最后一次一定是1

gap = gap / 3 + 1; // 9 8

for (int i = 0; i < n - gap; ++i)

{

int end = i;

int tmp = a[end + gap];

while (end >= 0)

{

if (tmp < a[end])

{

a[end + gap] = a[end];

end -= gap;

}

else

{

break;

}

}

a[end + gap] = tmp;

}

}

}

希爾排序的特性總結(jié)：

希爾排序是對(duì)直接插入排序的優(yōu)化。當(dāng)gap > 1時(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時(shí)，數(shù)組已經(jīng)接近有序的了，這樣就 會(huì)很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。我們實(shí)現(xiàn)后可以進(jìn)行性能測(cè)試的對(duì)比。希爾排序的時(shí)間復(fù)雜度不好計(jì)算，因?yàn)間ap的取值方法很多，導(dǎo)致很難去計(jì)算，因此在好些樹(shù)中給出的希爾排序的時(shí)間復(fù)雜度都不固定：《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)》— 嚴(yán)蔚敏 《數(shù)據(jù)結(jié)構(gòu)-用面相對(duì)象方法與C++描述》— 殷人昆

穩(wěn)定性：當(dāng)相同關(guān)鍵字的記錄被劃分到不同的字表時(shí)，可能會(huì)改變它們之前的相對(duì)排序，因此希爾排序是一種不穩(wěn)定的排序算法。

適用性：希爾排序算法僅適用于線性表為順序存儲(chǔ)的情況。

2.2 選擇排序

選擇排序的基本思想是：

每一趟（如第 i 趟）在后面 n - i + l ( i =1,2,…, n -1）個(gè)待排序元素中選取關(guān)鍵字最小的元素，作為有序子序列的第 i 個(gè)元素，直到第 n - l 趟做完，待排序元素只剩下1個(gè)，就不用再選了。

2.2.1直接選擇排序

選擇排序是一種簡(jiǎn)單直觀的排序算法，無(wú)論什么數(shù)據(jù)進(jìn)去都是 O(n2)的時(shí)間復(fù)雜度。所以用到它的時(shí)候，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間。

根據(jù)上面選擇排序的思想，可以很直觀地得出簡(jiǎn)單選擇排序算法的思想： 假設(shè)排序表為 L [1… n ]，第 i 趟排序即從 L [ i … n ］中選擇關(guān)鍵字最小的元素與 L ( i ）交換，每一趟排序可以確定一個(gè)元素的最終位置，這樣經(jīng)過(guò) n -1趟排序就可使得整個(gè)排序表有序。

算法步驟:

首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置。

再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。

重復(fù)第二步，直到所有元素均排序完畢。

動(dòng)態(tài)圖展示：

代碼如下：

// 任何情況都是O(N^2) 包括有序或接近有序

void SelectSort(int* a, int n)

{

int begin = 0, end = n - 1;

while (begin < end)

{

int mini = begin, maxi = begin;

for (int i = begin + 1; i <= end; ++i)

{

if (a[i] < a[mini])

{

mini = i;

}

if (a[i] > a[maxi])

{

maxi = i;

}

}

Swap(&a[begin], &a[mini]);

if (maxi == begin)

maxi = mini;

Swap(&a[end], &a[maxi]);

++begin;

--end;

}

}

直接選擇排序的特性總結(jié)：

空間效率：僅使用常數(shù)個(gè)輔助單元，故空間效率為 O (1)。 時(shí)間效率：從上述偽碼中不難看出，在簡(jiǎn)單選擇排序過(guò)程中，元素移動(dòng)的操作次數(shù)很少，不會(huì)超過(guò)3( n -1）次，最好的情況是移動(dòng)0次，此時(shí)對(duì)應(yīng)的表已經(jīng)有序；但元素間比較的次數(shù)與序列的初始狀態(tài)無(wú)關(guān)，始終是 n ( n -1)/2次，因此時(shí)間復(fù)雜度始終是 O ( n^2)。

穩(wěn)定性：在第 i 趟找到最小元素后，和第 i 個(gè)元素交換，可能會(huì)導(dǎo)致第1個(gè)元素與其含有相同關(guān)鍵字元素的相對(duì)位置發(fā)生改變。因此，簡(jiǎn)單選擇排序是一種不穩(wěn)定的排序方法。

2.2.2堆排序

在之前的博客中，我們已經(jīng)詳細(xì)了解了堆排序的概念以及運(yùn)用。具體大家可以閱讀：堆排序的詳解

2.3交換排序

基本思想：所謂交換，就是根據(jù)序列中兩個(gè)記錄鍵值的比較結(jié)果來(lái)對(duì)換這兩個(gè)記錄在序列中的位置。

交換排序的特點(diǎn)是：將鍵值較大的記錄向序列的尾部移動(dòng)，鍵值較小的記錄向序列的前部移動(dòng)。

2.3.1冒泡排序

冒泡排序（Bubble Sort）也是一種簡(jiǎn)單直觀的排序算法。它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢"浮"到數(shù)列的頂端。

作為最簡(jiǎn)單的排序算法之一，冒泡排序給我的感覺(jué)就像 Abandon 在單詞書(shū)里出現(xiàn)的感覺(jué)一樣，每次都在第一頁(yè)第一位，所以最熟悉。冒泡排序還有一種優(yōu)化算法，就是立一個(gè) flag，當(dāng)在一趟序列遍歷中元素沒(méi)有發(fā)生交換，則證明該序列已經(jīng)有序。但這種改進(jìn)對(duì)于提升性能來(lái)說(shuō)并沒(méi)有什么太大作用。

冒泡排序的基本思想是：

從后往前（或從前往后）兩兩比較相鄰元素的值，若為逆序（即 A [ i -1]> A [ i ])，則交換它們，直到序列比較完。我們稱它為第一趟冒泡，結(jié)果是將最小的元素交換到待排序列的第一個(gè)位置（或?qū)⒆畲蟮脑亟粨Q到待排序列的最后一個(gè)位置），關(guān)鍵字最小的元素如氣泡一般逐漸往上"漂浮"直至"水面"（或關(guān)鍵字最大的元素如石頭一般下沉至水底）。下一趟冒泡時(shí)，前一趟確定的最小元素不再參與比較，每趟冒泡的結(jié)果是把序列中的最小元素（或最大元素）放到了序列的最終位置．…．這樣最多做 n -1趟冒泡就能把所有元素排好序。

所示為冒泡排序的過(guò)程，第一趟冒泡時(shí)：27<49，不交換：13<27，不交換：76>13,交換：97>13，交換：65>13，交換；38>13，交換；49>13，交換。通過(guò)第一趟冒泡后，最小元素已交換到第一個(gè)位置，也是它的最終位置。第二趟冒泡時(shí)對(duì)剩余子序列采用同樣方法進(jìn)行排序，以此類推，到第五趟結(jié)束后沒(méi)有發(fā)生交換，說(shuō)明表已有序，冒泡排序結(jié)束。

算法步驟

比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。

對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。

針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

動(dòng)態(tài)圖展示如下：

代碼如下：

void BubbleSort(int* a, int n)

{

for (int j = 0; j < n; ++j)

{

int exchange = 0;

for (int i = 1; i < n-j; ++i)

{

if (a[i - 1] > a[i])

{

Swap(&a[i - 1], &a[i]);

exchange = 1;

}

}

// 一趟冒泡過(guò)程中，沒(méi)有發(fā)生交換，說(shuō)明已經(jīng)有序了，不需要再處理

if (exchange == 0)

{

break;

}

}

}

冒泡排序的性能分析如下：

空間效率：僅使用了常數(shù)個(gè)輔助單元，因而空間復(fù)雜度為 O (1)。

時(shí)間效率：當(dāng)初始序列有序時(shí)，顯然第一趟冒泡后 flag 依然為 false （本趟冒泡沒(méi)有元素交換），從而直接跳出循環(huán)，比較次數(shù)為 n -1，移動(dòng)次數(shù)為0，從而最好情況下的時(shí)間復(fù)雜度為 O ( n )：當(dāng)初始序列為逆序時(shí)，需要進(jìn)行 n - l 趟排序，第 i 趟排序要進(jìn)行 n - i 次關(guān)鍵字的比較，而且每次比較后都必須移動(dòng)元素3次來(lái)交換元素位置。這種情況下:

冒泡排序總的比較次數(shù)為n(n-1)/2，移動(dòng)次數(shù)為n(n-1)/2次；

從而，最壞情況下的時(shí)間復(fù)雜度為 O ( n^2)，其平均時(shí)間復(fù)雜度也為 O(n^2）。

穩(wěn)定性：冒泡排序是一種穩(wěn)定的排序方法。

注意：冒泡排序中所產(chǎn)生的有序子序列一定是全局有序的（不同于直接插入排序），也就是說(shuō)，有序子序列中的所有元素的關(guān)鍵字一定小于或大于無(wú)序子序列中所有元素的關(guān)鍵字，這樣每趟排序都會(huì)將一個(gè)元素放置到其最終的位置上。

2.3.2 快速排序(重點(diǎn)）

快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個(gè)項(xiàng)目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見(jiàn)。事實(shí)上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來(lái)。

快速排序使用分治法（Divide and conquer）策略來(lái)把一個(gè)串行（list）分為兩個(gè)子串行（sub-lists）。

快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用。本質(zhì)上來(lái)看，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法。

其基本思想為：

任取待排序元素序列中的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過(guò)程，直到所有元素都排列在相應(yīng)位置上為止。

1. hoare版本（即左右指針?lè)ǎ?/p>

思想：

一趟排序過(guò)程就是一個(gè)交替搜索和替換的過(guò)程。任取待排序元素序列中的某元素作為基準(zhǔn)值（一般是兩邊的元素，我們這里選擇最左邊），然后我們把key放到合適的位置，使得（左邊比key小，右邊比key大【升序】），讓最右邊的元素先移動(dòng)找比key小的，左邊找比key大的，然后交換left和right的值，直到left和right相遇即止，相遇后交換key和left（right）任意一個(gè)位置的值。

我們通過(guò)畫(huà)圖來(lái)進(jìn)行了解：

當(dāng)?shù)谝淮巫笥抑羔樝嘤龊蟮奈恢脮r(shí)，基準(zhǔn)值就被交換到了中間，接著呢繼續(xù)對(duì)左右區(qū)間進(jìn)行重復(fù)的操作，首先直至左區(qū)間有序后，會(huì)進(jìn)行回調(diào)；此時(shí)再去遞歸右區(qū)間，當(dāng)右區(qū)間也有序之后，那整體也就有序了

注意：

左邊做key,可以讓左邊先走嗎？

不可以左邊做key必須讓右邊先走，右邊(right)是找比key小的，找到小的停下來(lái)，即使相遇也能保證right位置的值小于key的

動(dòng)圖展示：

代碼如下：

// Hoare

int PartSort1(int* a, int begin, int end)

{

int mid = GetMidIndex(a, begin, end);

Swap(&a[begin], &a[mid]);

int left = begin, right = end;

int keyi = left;

while (left < right)

{

// 右邊先走，找小

while (left < right && a[right] >= a[keyi])

{

--right;

}

// 左邊再走，找大

while (left < right && a[left] <= a[keyi])

{

++left;

}

Swap(&a[left], &a[right]);

}

Swap(&a[left], &a[keyi]);

keyi = left;

return keyi;

}

大家分析上述代碼，會(huì)發(fā)現(xiàn)有缺陷的地方？

1.待排序列呈現(xiàn)有序的情況，如果key后面的每個(gè)數(shù)都比key小或大的話，那left向后面找或right向前面找，就會(huì)產(chǎn)生越界訪問(wèn)的問(wèn)題，為了防止這樣情況的產(chǎn)生，我們選擇在if語(yǔ)句的判斷部分加個(gè)邏輯與&&保證left小于right，以免產(chǎn)生越界訪問(wèn)的問(wèn)題。

2.快速排序除了對(duì)【有序序列】進(jìn)行排序會(huì)退化之外，還有一點(diǎn)就是它需要進(jìn)行層層遞歸，那既然是遞歸，就需要調(diào)用函數(shù)；既然要調(diào)用函數(shù)，那就需要建立棧幀，一旦建立棧幀會(huì)出現(xiàn)棧溢出的情況。

第一種方法就是三數(shù)取中，三數(shù)取中就是為了讓我們選取的key在序列中的位置盡量靠中間.?三數(shù)取中，當(dāng)中的三數(shù)指的是：最左邊的數(shù)、最右邊的數(shù)以及中間位置的數(shù)。三數(shù)取中就是取這三個(gè)數(shù)當(dāng)中，值的大小居中的那個(gè)數(shù)作為該趟排序的key。這就確保了我們所選取的數(shù)不會(huì)是序列中的最大或是最小值了。

代碼如下：

// 三數(shù)取中

// begin mid end

int GetMidIndex(int* a, int begin, int end)

{

int mid = (begin + end) / 2;

if (a[begin] < a[mid])

{

if (a[mid] < a[end])

{

return mid;

}

else if (a[begin] > a[end])

{

return begin;

}

else

{

return end;

}

}

else // a[begin] > a[mid]

{

if (a[mid] > a[end])

{

return mid;

}

else if (a[begin] < a[end])

{

return begin;

}

else

{

return end;

}

}

}

注意： 當(dāng)大小居中的數(shù)不在序列的最左或是最右端時(shí)，我們不是就以居中數(shù)的位置作為key的位置，而是將key的值與最左端的值進(jìn)行交換，這樣key就還是位于最左端了，所寫(xiě)代碼就無(wú)需改變，而只需在單趟排序代碼開(kāi)頭加上以下兩句代碼即可：

int midIndex = GetMidIndex(a, begin, end);//獲取大小居中的數(shù)的下標(biāo)

Swap(&a[begin], &a[midIndex]);//將該數(shù)與序列最左端的數(shù)據(jù)交換

//以下代碼保持不變...

對(duì)于三數(shù)取中法，是在開(kāi)頭優(yōu)化； 而第二種小區(qū)間優(yōu)化法，則是在結(jié)尾優(yōu)化

小區(qū)間優(yōu)化是為了讓遞歸深度不要太深，因?yàn)閿?shù)據(jù)量過(guò)大以后，我們遞歸的深度就會(huì)增加，遞歸建立的棧幀數(shù)量會(huì)隨著遞歸深度的增加而增加，又因?yàn)闂？臻g本身就小，很容易造成棧溢出的問(wèn)題。當(dāng)遞歸區(qū)間的數(shù)據(jù)量較小時(shí)，我們不采用遞歸解決他們，而是換成直接插入的方法來(lái)解決較小數(shù)據(jù)量的排序。

//小區(qū)間優(yōu)化

if ((end - begin + 1) < 15)

{

//在數(shù)據(jù)量少的時(shí)候改用直接插入排序

InsertSort(a + begin, end - begin + 1);

}

2.挖坑法

思想：

1、選出一個(gè)數(shù)據(jù)（一般是最左邊或是最右邊的）存放在key變量中，在該數(shù)據(jù)位置形成一個(gè)坑。 2、還是定義一個(gè)left和一個(gè)right，left從左向右走，right從右向左走。（若在最左邊挖坑，則需要R先走；若在最右邊挖坑，則需要L先走）。 3、在走的過(guò)程中，若R遇到小于key的數(shù)，則將該數(shù)拋入坑位，并在此處形成一個(gè)坑位，這時(shí)left再向后走，若遇到大于key的數(shù)，則將其拋入坑位，又形成一個(gè)坑位，如此循環(huán)下去，直到最終L和R相遇，這時(shí)將key拋入坑位即可。（選取最左邊的作為坑位）

經(jīng)過(guò)一次單趟排序，最終也使得key左邊的數(shù)據(jù)全部都小于key，key右邊的數(shù)據(jù)全部都大于key。

然后也是將key的左序列和右序列再次進(jìn)行這種單趟排序，如此反復(fù)操作下去，直到左右序列只有一個(gè)數(shù)據(jù)，或是左右序列不存在時(shí)，便停止操作。

動(dòng)態(tài)展示：

代碼如下：

// 挖坑法

int PartSort2(int* a, int begin, int end)

{

int mid = GetMidIndex(a, begin, end);

Swap(&a[begin], &a[mid]);

int left = begin, right = end;

int key = a[left];

int hole = left;

while (left < right)

{

// 右邊找小，填到左邊坑里面

while (left < right && a[right] >= key)

{

--right;

}

a[hole] = a[right];

hole = right;

// 左邊找大，填到右邊坑里面

while (left < right && a[left] <= key)

{

++left;

}

a[hole] = a[left];

hole = left;

}

a[hole] = key;

return hole;

}

3.前后指針?lè)?/p>

思想：

前后指針?lè)ǖ膯翁伺判虻幕静襟E如下： ? 1、選出一個(gè)key，一般是最左邊或是最右邊的。 2、起始時(shí)，prev指針指向序列開(kāi)頭，cur指針指向prev+1。 3、若cur指向的內(nèi)容小于key，則prev先向后移動(dòng)一位，然后交換prev和cur指針指向的內(nèi)容，然后cur指針++；若cur指向的內(nèi)容大于key，則cur指針直接++。如此進(jìn)行下去，直到cur指針越界，此時(shí)將key和prev指針指向的內(nèi)容交換即可。

經(jīng)過(guò)一次單趟排序，最終也能使得key左邊的數(shù)據(jù)全部都小于key，key右邊的數(shù)據(jù)全部都大于key。

然后也還是將key的左序列和右序列再次進(jìn)行這種單趟排序，如此反復(fù)操作下去，直到左右序列只有一個(gè)數(shù)據(jù)，或是左右序列不存在時(shí)，便停止操作。

單趟的動(dòng)圖演示：

上述遞歸實(shí)現(xiàn)的局限性可能在于： 當(dāng)數(shù)據(jù)量特別大時(shí)，可能會(huì)導(dǎo)致棧溢出(棧漲的速度為logn，也可能是我多慮了，漲地其實(shí)挺慢的)。 為了解決上面可能出現(xiàn)的問(wèn)題，我們可以將遞歸實(shí)現(xiàn)轉(zhuǎn)換為非遞歸實(shí)現(xiàn)，我們知道任何遞歸的過(guò)程都可以轉(zhuǎn)化為一個(gè)迭代的過(guò)程，而轉(zhuǎn)化的關(guān)鍵在于如何使用迭代來(lái)模擬整個(gè)遞歸的處理。

觀察上面的遞歸處理過(guò)程，我們可以看到：每一次排序函數(shù)的調(diào)用都會(huì)再次重新調(diào)用兩次新的排序函數(shù)，然后系統(tǒng)會(huì)按照調(diào)用順序一步一步地進(jìn)行處理和返回，而調(diào)用排序函數(shù)的關(guān)鍵在于必須將排序的范圍告訴函數(shù)。

這個(gè)過(guò)程很像一個(gè)排隊(duì)處理的過(guò)程，于是我們可以使用隊(duì)列進(jìn)行遞歸的模擬，而隊(duì)列中的信息存儲(chǔ)要處理的范圍即可。當(dāng)隊(duì)列不為空時(shí)，表示還有范圍未處理；隊(duì)列為空時(shí)，表示所有的范圍都已經(jīng)處理完畢，也即確定了所有元素的位置，完成了排序工作。

我們利用棧的相關(guān)思想來(lái)進(jìn)行實(shí)現(xiàn)：

void QuickSortNonR(int* a, int left, int right)

{

Stack st;

StackInit(&st);

StackPush(&st, left);

StackPush(&st, right);

while (StackEmpty(&st) != 0)

{

right = StackTop(&st);

StackPop(&st);

left = StackTop(&st);

StackPop(&st);

if(right - left <= 1)

continue;

int div = PartSort1(a, left, right);

// 以基準(zhǔn)值為分割點(diǎn)，形成左右兩部分：[left, div) 和 [div+1, right)

StackPush(&st, div+1);

StackPush(&st, right);

StackPush(&st, left);

StackPush(&st, div);

}

StackDestroy(&s);

}

快速排序算法的性能分析如下：

空間效率：由于快速排序是遞歸的，需要借助一個(gè)遞歸工作找來(lái)保存每層遞歸調(diào)用的必要信息，其容量應(yīng)與遞歸調(diào)用的最大深度一致。最好情況下為 O ( logzn )；最壞情況下，因?yàn)橐M(jìn)行 n - l 次遞歸調(diào)用，所以棧的深度為 O ( n )：平均情況下，棧的深度為 O ( logn)。

時(shí)間效率：快速排序的運(yùn)行時(shí)間與劃分是否對(duì)稱有關(guān)，快速排序的最壞情況發(fā)生在兩個(gè)區(qū)域分別包含 n -1個(gè)元素和0個(gè)元素時(shí)，這種最大限度的不對(duì)稱性若發(fā)生在每層遞歸上，即對(duì)應(yīng)于初始排序表基本有序或基本逆序時(shí)，就得到最壞情況下的時(shí)間復(fù)雜度為 O ( n^2)。

有很多方法可以提高算法的效率：

一種方法是盡量選取一個(gè)可以將數(shù)據(jù)中分的樞軸元素，如從序列的頭尾及中間選取三個(gè)元素，再取這三個(gè)元素的中間值作為最終的樞軸元素：

或者隨機(jī)地從序列的頭尾及中間選取三個(gè)元素，再取這三個(gè)元素的中間值作為最終的樞軸元素；有隨機(jī)吧從當(dāng)前表中選取樞軸元素，這樣做可使得最壞情況在實(shí)際排序中幾乎不會(huì)發(fā)生。

在最理想的狀態(tài)下，即 Partition (）可能做到最平衡的劃分，得到的兩個(gè)子問(wèn)題的大小都不可能大于 n /2，在這種情況下，快速排序的運(yùn)行速度將大大提升，此時(shí)，時(shí)間復(fù)雜度為 O (nlog2n)。好在快速排序平均情況下的運(yùn)行時(shí)間與其最佳情況下的運(yùn)行時(shí)間很接近，而不是接近其最壞情況下的運(yùn)行時(shí)間?？焖倥判蚴撬袃?nèi)部排序算法中平均性能最優(yōu)的排序算法。

穩(wěn)定性：在劃分算法中，若右端區(qū)間有兩個(gè)關(guān)鍵字相同，且均小于基準(zhǔn)值的記錄，則在交換到左端區(qū)間后，它們的相對(duì)位置會(huì)發(fā)生變化，即快速排序是一種不穩(wěn)定的排序方法。例如，表 L =(3,2,2)，經(jīng)過(guò)一趟排序后 L =(2,2,3)，最終排序序列也是 L =(2,2,3)，顯然，2與2的相對(duì)次序已發(fā)生了變化。

注意：在快速排序算法中，并不產(chǎn)生有序子序列，但每趟排序后會(huì)將樞軸（基準(zhǔn)）元素放到其最終的位置上。

2.4 歸并排序

歸并排序與上述基于交換、選擇等排序的思想不一樣，"歸并"的含義是將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表。假定待排序表含有 n 個(gè)記錄，則可將其視為 n 個(gè)有序的子表，每個(gè)子表的長(zhǎng)度為1，然后兩兩歸并，得到「 n /27個(gè)長(zhǎng)度為2或」的有序表；繼續(xù)兩兩歸并．…．如此重復(fù)，直到合并成一個(gè)長(zhǎng)度為 n 的有序表為止，這種排序方法稱為2路歸并排序。

兩路歸并核心步奏：

作為一種典型的分而治之思想的算法應(yīng)用，歸并排序的實(shí)現(xiàn)由兩種方法：

自上而下的遞歸（所有遞歸的方法都可以用迭代重寫(xiě)，所以就有了第 2 種方法）； 自下而上的迭代；

以下為一個(gè)兩路歸并的例子：

算法步驟：

申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列；

設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置；

比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置；

重復(fù)步驟 3 直到某一指針達(dá)到序列尾；

將另一序列剩下的所有元素直接復(fù)制到合并序列尾。

遞歸版本：

// 時(shí)間復(fù)雜度：O(N*logN)

// 空間復(fù)雜度：O(N)

// [begin, end]

void _MergeSort(int* a, int begin, int end, int* tmp)

{

if (begin >= end)

return;

int mid = (begin + end) / 2;

// [begin, mid] [mid+1, end] 遞歸讓子區(qū)間有序

_MergeSort(a, begin, mid, tmp);

_MergeSort(a, mid+1, end, tmp);

// 歸并[begin, mid] [mid+1, end]

//...

int begin1 = begin, end1 = mid;

int begin2 = mid+1, end2 = end;

int i = begin;

while (begin1 <= end1 && begin2 <= end2)

{

if (a[begin1] <= a[begin2])

{

tmp[i++] = a[begin1++];

}

else

{

tmp[i++] = a[begin2++];

}

}

while (begin1 <= end1)

{

tmp[i++] = a[begin1++];

}

while (begin2 <= end2)

{

tmp[i++] = a[begin2++];

}

memcpy(a + begin, tmp + begin, sizeof(int)*(end - begin + 1));

}

void MergeSort(int* a, int n)

{

int* tmp = (int*)malloc(sizeof(int)*n);

if (tmp == NULL)

{

perror("malloc fail");

exit(-1);

}

_MergeSort(a, 0, n - 1, tmp);

free(tmp);

tmp = NULL;

}

非遞歸版本：

歸并排序的非遞歸算法并不需要借助棧來(lái)完成，我們只需要控制每次參與合并的元素個(gè)數(shù)即可，最終便能使序列變?yōu)橛行颍?? 當(dāng)然，以上例子是一個(gè)待排序列長(zhǎng)度比較特殊的例子，我們?nèi)羰窍雽?xiě)出一個(gè)廣泛適用的程序，必定需要考慮到某些極端情況： 情況一： ?當(dāng)最后一個(gè)小組進(jìn)行合并時(shí)，第二個(gè)小區(qū)間存在，但是該區(qū)間元素個(gè)數(shù)不夠gap個(gè)，這時(shí)我們需要在合并序列時(shí)，對(duì)第二個(gè)小區(qū)間的邊界進(jìn)行控制。 ? 情況二： ?當(dāng)最后一個(gè)小組進(jìn)行合并時(shí)，第二個(gè)小區(qū)間不存在，此時(shí)便不需要對(duì)該小組進(jìn)行合并。 ? 情況三： ?當(dāng)最后一個(gè)小組進(jìn)行合并時(shí)，第二個(gè)小區(qū)間不存在，并且第一個(gè)小區(qū)間的元素個(gè)數(shù)不夠gap個(gè)，此時(shí)也不需要對(duì)該小組進(jìn)行合并。 ? 只要把控好這三種特殊情況，寫(xiě)出歸并排序的非遞歸算法便輕而易舉了。

代碼如下：

void MergeSortNonR(int* a, int n)

{

int* tmp = (int*)malloc(sizeof(int)*n);

if (tmp == NULL)

{

perror("malloc fail");

exit(-1);

}

// 歸并每組數(shù)據(jù)個(gè)數(shù)，從1開(kāi)始，因?yàn)?個(gè)認(rèn)為是有序的，可以直接歸并

int rangeN = 1;

while (rangeN < n)

{

for (int i = 0; i < n; i += 2 * rangeN)

{

// [begin1,end1][begin2,end2] 歸并

int begin1 = i, end1 = i + rangeN - 1;

int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;

printf("[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);

int j = i;

// end1 begin2 end2 越界

// 修正區(qū)間 ->拷貝數(shù)據(jù) 歸并完了整體拷貝 or 歸并每組拷貝

if (end1 >= n)

{

end1 = n - 1;

// 不存在區(qū)間

begin2 = n;

end2 = n - 1;

}

else if (begin2 >= n)

{

// 不存在區(qū)間

begin2 = n;

end2 = n - 1;

}

else if (end2 >= n)

{

end2 = n - 1;

}

while (begin1 <= end1 && begin2 <= end2)

{

if (a[begin1] <= a[begin2])

{

tmp[j++] = a[begin1++];

}

else

{

tmp[j++] = a[begin2++];

}

}

while (begin1 <= end1)

{

tmp[j++] = a[begin1++];

}

while (begin2 <= end2)

{

tmp[j++] = a[begin2++];

}

}

// 也可以整體歸并完了再拷貝

memcpy(a, tmp, sizeof(int)*(n));

rangeN *= 2;

}

free(tmp);

tmp = NULL;

}

動(dòng)態(tài)圖展示：

2路歸并排序算法的性能分析如下：

空間效率： Merge (）操作中，輔助空間剛好為 n 個(gè)單元，所以算法的空間復(fù)雜度為 O ( n )。 時(shí)間效率：每趟歸并的時(shí)間復(fù)雜度為 O ( n )，共需進(jìn)行「 logznl 趟歸并，所以算法的時(shí)間復(fù)雜度為 O ( nlogn ).

穩(wěn)定性：由于 Merge (）操作不會(huì)改變相同關(guān)鍵字記錄的相對(duì)次序，所以2路歸并排序算法是一種穩(wěn)定的排序方法。

2.5 計(jì)數(shù)排序

思想： 計(jì)數(shù)排序又稱為鴿巢原理，是對(duì)哈希直接定址法的變形應(yīng)用。 顧名思義，該算法不是通過(guò)比較數(shù)據(jù)的大小來(lái)進(jìn)行排序的，而是通過(guò)統(tǒng)計(jì)數(shù)組中相同元素出現(xiàn)的次數(shù)，然后通過(guò)統(tǒng)計(jì)的結(jié)果將序列回收到原來(lái)的序列中。操作步驟：

統(tǒng)計(jì)相同元素出現(xiàn)次數(shù)根據(jù)統(tǒng)計(jì)的結(jié)果將序列回收到原來(lái)的序列中

計(jì)數(shù)排序的特征

當(dāng)輸入的元素是 n 個(gè) 0 到 k 之間的整數(shù)時(shí)，它的運(yùn)行時(shí)間是 Θ(n + k)。計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。由于用來(lái)計(jì)數(shù)的數(shù)組C的長(zhǎng)度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值與最小值的差加上1），這使得計(jì)數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量時(shí)間和內(nèi)存。

注：計(jì)數(shù)排序只適用于數(shù)據(jù)范圍較集中的序列的排序，若待排序列的數(shù)據(jù)較分散，則會(huì)造成空間浪費(fèi)，并且計(jì)數(shù)排序只適用于整型排序，不適用與浮點(diǎn)型排序。

算法的步驟如下： （1）找出待排序的數(shù)組中最大和最小的元素 （2）統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng) （3）對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開(kāi)始，每一項(xiàng)和前一項(xiàng)相加） （4）反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1

動(dòng)態(tài)展示：

代碼如下：

//計(jì)數(shù)排序

void CountSort(int* a, int n)

{

int min = a[0];//記錄數(shù)組中的最小值

int max = a[0];//記錄數(shù)組中的最大值

for (int i = 0; i < n; i++)

{

if (a[i] < min)

min = a[i];

if (a[i] > max)

max = a[i];

}

int range = max - min + 1;//min和max之間的自然數(shù)個(gè)數(shù)（包括min和max本身）

int* count = (int*)calloc(range, sizeof(int));//開(kāi)辟可儲(chǔ)存range個(gè)整型的內(nèi)存空間，并將內(nèi)存空間置0

if (count == NULL)

{

printf("malloc fail\n");

exit(-1);

}

//統(tǒng)計(jì)相同元素出現(xiàn)次數(shù)（相對(duì)映射）

for (int i = 0; i < n; i++)

{

count[a[i] - min]++;

}

int i = 0;

//根據(jù)統(tǒng)計(jì)結(jié)果將序列回收到原來(lái)的序列中

for (int j = 0; j < range; j++)

{

while (count[j]--)

{

a[i++] = j + min;

}

}

free(count);//釋放空間

}

計(jì)數(shù)排序算法的性能分析如下：

計(jì)數(shù)排序在數(shù)據(jù)范圍集中時(shí)，效率很高，但是適用范圍及場(chǎng)景有限。時(shí)間復(fù)雜度：O(MAX(N,范圍))空間復(fù)雜度：O(范圍)穩(wěn)定性：穩(wěn)定

3.各種內(nèi)部排序算法比較及運(yùn)用

3.1內(nèi)部排序算法的比較

前面討論的排序算法很多，對(duì)各算法的比較也是愛(ài)考的內(nèi)容。一般基于三個(gè)因素進(jìn)行對(duì)比：時(shí)空復(fù)雜度、算法的穩(wěn)定性、算法的過(guò)程特征。

從時(shí)間復(fù)雜度看：

簡(jiǎn)單選擇排序、直接插入排序和冒泡排序平均情況下的時(shí)間復(fù)雜度都為 O ( n^2)，且實(shí)現(xiàn)過(guò)程也較簡(jiǎn)單.

直接插入排序和冒泡排序最好情況下的時(shí)間復(fù)雜度可以達(dá)到 O ( n )

而簡(jiǎn)單選擇排序則與序列的初始狀態(tài)無(wú)關(guān)。 希爾排序作為插入排序的拓展，對(duì)較大規(guī)模的排序都可以達(dá)到很高的效率，但目前未得出其精確的漸近時(shí)間。 堆排序利用了一種稱為堆的數(shù)據(jù)結(jié)構(gòu)，可在線性時(shí)間內(nèi)完成建堆，且在 O ( nlogn ）內(nèi)完成排序過(guò)程。

快速排序基于分治的思想，雖然最壞情況下快速排序時(shí)間會(huì)達(dá)到 O ( n )，但快速排序平均性能可以達(dá)到 O ( nlogn )，在實(shí)際應(yīng)用中常常優(yōu)于其他排序算法。

歸并排序同樣基于分治的思想，但由于其分割子序列與初始序列的排列無(wú)關(guān)，因此它的最好、最壞和平均時(shí)間復(fù)雜度均為 O ( nlogn )。

從空間復(fù)雜度看：

簡(jiǎn)單選擇排序、插入排序、冒泡排序、希爾排序和堆排序都僅需要借助常數(shù)個(gè)輔助空間。

快速排序在空間上只使用一個(gè)小的輔助棧，用于實(shí)現(xiàn)遞歸，平均情況下大小為 O ( logn )，當(dāng)然在最壞情況下可能會(huì)增長(zhǎng)到 O ( n )。

2路歸并排序在合并操作中需要借助較多的輔助空間用于元素復(fù)制，大小為 O ( n )，雖然有方法能克服這個(gè)缺點(diǎn)，但其代價(jià)是算法會(huì)很復(fù)雜而且時(shí)間復(fù)雜度會(huì)增加。

從穩(wěn)定性看：插入排序、冒泡排序、歸并排序和基數(shù)排序是穩(wěn)定的排序方法，而簡(jiǎn)單選擇排序、快速排序、希爾排序和堆排序都是不穩(wěn)定的排序方法。平均時(shí)間復(fù)雜度為 O ( nlogn ）的穩(wěn)定排序算法只有歸并排序，對(duì)于不穩(wěn)定的排序方法，只要舉出一個(gè)不穩(wěn)定的實(shí)例即可。對(duì)于排序方法的穩(wěn)定性，小伙伴們應(yīng)能從算法本身的原理上去理解，而不應(yīng)拘泥于死記硬背。

排序算法復(fù)雜度及穩(wěn)定性分析：

3.2內(nèi)部排序算法的運(yùn)用

通常情況，對(duì)排序算法的比較和應(yīng)用應(yīng)考慮以下情況。

1）選取排序方法需要考慮的因素

①待排序的元素?cái)?shù)目 n ②元素本身信息量的大小。 ③關(guān)鍵字的結(jié)構(gòu)及其分布情況。 ④穩(wěn)定性的要求。 ⑤語(yǔ)言工具的條件，存儲(chǔ)結(jié)構(gòu)及輔助空間的大小等。

2）排序算法小結(jié)

①若 n 較小，可采用直接插入排序或簡(jiǎn)單選擇排序。由于直接插入排序所需的記錄移動(dòng)次數(shù)較簡(jiǎn)單選擇排序的多，因而當(dāng)記錄本身信息量較大時(shí)，用簡(jiǎn)單選擇排序較好。

②若文件的初始狀態(tài)已按關(guān)鍵字基本有序，則選用直接插入或冒泡排序?yàn)橐恕?/p>

③若 n 較大，則應(yīng)采用時(shí)間復(fù)雜度為 O ( nlogn ）的排序方法：【快速排序、堆排序或歸并排序】。快速排序被認(rèn)為是目前基于比較的內(nèi)部排序方法中最好的方法，當(dāng)待排序的關(guān)鍵字隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短。堆排序所需的輔助空間少于快速排序，并且不會(huì)出現(xiàn)快速排序可能出現(xiàn)的最壞情況，這兩種排序都是不穩(wěn)定的。若要求排序穩(wěn)定且時(shí)間復(fù)雜度為 O ( nlogn )，則可選用歸并排序。

④在基于比較的排序方法中，每次比較兩個(gè)關(guān)鍵字的大小之后，僅出現(xiàn)兩種可能的轉(zhuǎn)移，因此可以用一棵二叉樹(shù)來(lái)描述比較判定過(guò)程，由此可以證明：當(dāng)文件的 n 個(gè)關(guān)鍵字隨機(jī)分布時(shí)，任何借助于"比較"的排序算法，至少需要 O ( nlogn / n ）的時(shí)間。

⑥若 n 很大，記錄的關(guān)鍵字位數(shù)較少所可以分解時(shí)，采用基數(shù)排序較好。

⑥當(dāng)記錄本身信息量較大時(shí)，為避免耗費(fèi)大量時(shí)間移動(dòng)記錄，可用鏈表作為存儲(chǔ)結(jié)構(gòu)。

4 選擇題講解

1.有字符序列 FBJGEAIDCH，現(xiàn)在打算對(duì)它按字母的字典順序用希爾排序進(jìn)行排序，那么在第一趟后（步長(zhǎng)為5）的序列為（ ） A.CAEBFDIGJH B.AIDCHFBJGE C.ABDCEFIJGH D.BFJGEAIDCH

解答：

希爾排序按照步長(zhǎng)把元素進(jìn)行小組劃分，每個(gè)小組元素進(jìn)行插入排序。

所以如果步長(zhǎng)為5，則整個(gè)數(shù)組被會(huì)劃分成5組數(shù)據(jù)：

FA BI JD GC EH

所以一趟排序之后的結(jié)果為：

ABDCEFIJGH 所以選C

2.下列排序方法中，每一趟排序結(jié)束時(shí)都至少能夠確定一個(gè)元素最終位置的方法是（ ）

① 選擇排序 ② 歸并排序 ③ 快速排序 ④ 堆排序

A.①④ B.①②④ C.①③④ D.①②③④

解析：

選擇排序每次選一個(gè)最值，放在最終的位置

快速排序每次基準(zhǔn)值的位置也可以確定

堆排序每次堆頂元素的位置也可以確定

所以這三種方法都可以每次至少確定一個(gè)元素的位置

而歸并排序每次都需要對(duì)n個(gè)元素重新確定位置，所以不能保證每次都能確定一個(gè)元素位置，有可能每次排序所有元素的位置都為發(fā)生變化。

所以選C

3.以下哪種排序算法對(duì)[1, 3, 2, 4, 5, 6, 7, 8, 9]進(jìn)行排序最快（ ） A.直接插入排序 B.快速排序 C.歸并排序 D.堆排序

解析：

次序列接近有序，所以如果是插入排序，時(shí)間復(fù)雜度逼近O(n)

快排： 逼近O(n^2)

歸并和堆排仍然是nlogn

所以選A

4.對(duì)數(shù)字序列28 16 32 12 60 2 5 72進(jìn)行升序的快速排序（以第一個(gè)關(guān)鍵碼為基準(zhǔn)的方法），一次劃分后的結(jié)果為（ ） A.2 5 12 16 28 60 32 72 B.2 16 5 12 28 60 32 72 C.2 16 12 5 28 60 32 72 D.5 16 2 12 28 32 60 72

解析：

快速排序以基準(zhǔn)值為中心，對(duì)元素進(jìn)行劃分，這里以28為基準(zhǔn)值，則小于28的和大于28的進(jìn)行交換，完成一次劃分

首先：32和5交換： 28 16 5 12 60 2 32 72

然后60和2交換： 28 16 5 12 2 60 32 72

最后28和最后一個(gè)小于28的元素進(jìn)行交換：

2 16 5 12 28 60 32 72

5.使用選擇排序?qū)﹂L(zhǎng)度為100的數(shù)組進(jìn)行排序，則比較的次數(shù)為（ ） A.5050 B.4950 C.4851 D.2475

解析：

選擇排序，每次都要在未排序的所有元素中找到最值，

如果有n個(gè)元素，則

第一次比較次數(shù)： n - 1

第二次比較次數(shù)： n - 2

…

第n - 1次比較次數(shù)： 1

所有如果n = 100

則比較次數(shù)的總和：99 + 98 + … + 1

共4950次。

好了，小伙伴們，以上就是排序的全部知識(shí)內(nèi)容了。如果對(duì)大家有幫助希望多多支持喲?。。?/p>

柚子快報(bào)激活碼778899分享：【排序算法】數(shù)據(jù)結(jié)構(gòu)排序詳解

http://yzkb.51969.com/

相關(guān)閱讀