目標(biāo)

1）?使用下列方法將一個(gè)數(shù)組按升序排序：歸并排序、快速排序和基數(shù)排序

2）?評(píng)估排序的效率，討論不同的方法的相對(duì)效率

?

目錄

?9.1 歸并排序

　　9.1.1 歸并數(shù)組

　　9.1.2 遞歸歸并排序

　　9.1.3 歸并排序的效率

　　9.1.4 迭代歸并排序

　　9.1.5 Java類庫中的歸并排序

9.2 快速排序

　　9.2.1 快速排序的效率

　　9.2.2 創(chuàng)建劃分

　　9.2.3 實(shí)現(xiàn)快速排序

　　9.2.4?Java類庫中的快速排序?

9.3 基數(shù)排序

　　9.3.1 基數(shù)排序的偽代碼

　　9.3.2 基數(shù)排序的效率

9.4 算法比較

小結(jié)

?

　　排序小數(shù)組時(shí)，之前的排序算法已經(jīng)足夠了，想排序一個(gè)更大的數(shù)組，那些算法可能也是一個(gè)合理的選擇。插入排序是對(duì)鏈?zhǔn)焦?jié)點(diǎn)鏈進(jìn)行排序的好方法。當(dāng)需要對(duì)頻繁地對(duì)非常大的數(shù)組進(jìn)行排序時(shí)，那些方法花時(shí)間太多。

?

9.1 歸并排序

　　歸并排序（merge sort）將數(shù)組分為兩半，分別對(duì)兩半進(jìn)行排序，然后將它們合并為一個(gè)有序的數(shù)組。歸并排序算法常常用遞歸方式來描述。遞歸常用同一問題的更小版本來表示解決問題的方案。當(dāng)你將問題劃分為兩個(gè)或多個(gè)更小的但獨(dú)立的問題時(shí)，解決每個(gè)新問題，然后將它們的方案合并為解決原始問題的方案，這個(gè)策略稱為分治（divide and conquer）算法。即，將問題劃分為小塊，然后攻克每個(gè)小塊以達(dá)成解決方案。

　　當(dāng)用遞歸表示時(shí)，分治算法含有兩個(gè)或多個(gè)遞歸調(diào)用。

?

9.1.1 歸并數(shù)組

　　歸并兩個(gè)有序數(shù)組，只需從頭開始處理到末尾，將一個(gè)數(shù)組中的項(xiàng)與另一個(gè)數(shù)組中的項(xiàng)進(jìn)行比較，較小的項(xiàng)復(fù)制到新的數(shù)組中。

?

9.1.2 遞歸歸并排序

算法

　　在歸并排序中，歸并兩個(gè)有序數(shù)組，實(shí)際上它們是原始數(shù)組的兩半。即，將數(shù)組分為兩半，排序每一半，然后將這兩段有序部分合并到第二個(gè)臨時(shí)數(shù)組中，然后將臨時(shí)數(shù)組復(fù)制回原始數(shù)組中。

　　歸并排序有下列遞歸形式：

Algorithm mergeSort(a, tempArray, first, last) // 遞歸地排序數(shù)組項(xiàng)a[first]到a[last] if (first < last){mid = first + (last - first) / 2mergeSort(a, tempArray, first, mid)mergeSort(a, tempArray, mid+1, last)使用數(shù)組tempArray合并有序的兩半a[first…mid]和a[mid_1…last] }

　　注意：算法沒有處理少于或等于一項(xiàng)的數(shù)組。

　　下列偽代碼描述了歸并步驟

Algorithm merge(a, tempArray, first, mid, last) // 合并相鄰的子數(shù)組a[first…mid]和a[mid+1…last] beginHalf1 = first endHalf1 = mid beginHalf2 = mid+1 endHalf2 = last // 當(dāng)兩個(gè)子數(shù)組都不空時(shí)，讓一個(gè)子數(shù)組中的項(xiàng)與另一個(gè)子數(shù)組中的項(xiàng)進(jìn)行比較 // 然后將較小的項(xiàng)復(fù)制到臨時(shí)數(shù)組中 index = 0 // tempArray中下一個(gè)可用的位置 while( (beginHalf1 <= endHalf1) 和 (beginHalf2 <= endHalf2) ){if(a[beginHalf1] <= a[beginHalf2]){tempArray[index] = a[beginHalf1]beginHalf1++ } else{tempArray[index] = a[beginHalf2]beginHalf2++ } index++ } // 斷言：一個(gè)子數(shù)組已經(jīng)全部復(fù)制到tempArray中 將另一個(gè)子數(shù)組中的剩余項(xiàng)復(fù)制到tempArray中 將tempArray中的項(xiàng)復(fù)制到數(shù)組a中

跟蹤算法中的步驟

　　當(dāng)對(duì)數(shù)組的兩半調(diào)用mergeSort時(shí)會(huì)發(fā)生什么。

?

圖 1 遞歸調(diào)用的效果及歸并排序過程中的合并

　　箭頭上的數(shù)字表示遞歸調(diào)用及合并的次序。第一次合并發(fā)生在4次遞歸調(diào)用mergeSort之后及其他遞歸調(diào)用mergeSort之前。所以遞歸調(diào)用mergeSort和merge是交織在一起的。真正的排序是發(fā)生在合并步驟而不是發(fā)生在遞歸調(diào)用步驟。

　　注：歸并排序在合并步驟中重排數(shù)組中的項(xiàng)。

實(shí)現(xiàn)說明

　　注意應(yīng)該只分配一次臨時(shí)數(shù)組。因?yàn)閿?shù)組是實(shí)現(xiàn)細(xì)節(jié)，所以也許會(huì)冒險(xiǎn)將空間分配隱藏在方法merge中。但是，因?yàn)槊看芜f歸調(diào)用mergeSort時(shí)都會(huì)調(diào)用merge，所以這個(gè)方法會(huì)導(dǎo)致分配臨時(shí)數(shù)組及初始化很多次。我們可以在下列共有mergeSort方法中分配一個(gè)臨時(shí)數(shù)組，然后將它傳給之前給出的偽代碼的私有mergeSort方法：

public static <T extends Comparable<? super T>> void mergeSort(T[] a, int first, int last) {// The cast is safe because the new array contains null entries@SuppressWarnings("unchecked")T[] tempArray = (T[])new Comparable<?>[a.length]; // Unchecked castmergeSort(a, tempArray, first, last); } // end mergeSort

　　？ super T 表示T的任意父類。當(dāng)我們分配Comparable對(duì)象的數(shù)組時(shí)，使用了通配符？來表示任意的對(duì)象。然后將數(shù)組轉(zhuǎn)型為類型T對(duì)象的數(shù)組。

?

9.1.3 歸并排序的效率

　　一般地，如果n是2^k次，就會(huì)發(fā)生k層遞歸調(diào)用。

　　合并步驟，真正工作所在。在共有n項(xiàng)的兩個(gè)子段中，合并步驟最多進(jìn)行n-1次比較。每次合并還需要向臨時(shí)數(shù)組的n次移動(dòng)及移回原始數(shù)組的n次移動(dòng)。總計(jì)，每次合并最多需要3n-1次操作。

　　每次調(diào)用mergeSort時(shí)需要調(diào)用merge一次。作為調(diào)用mergeSort的結(jié)果，合并操作最多需要3n-1次操作。這是O(n)的。兩次遞歸調(diào)用mergeSort導(dǎo)致兩次調(diào)用merge。每次調(diào)用最多用3n/2-1次操作合并n/2項(xiàng)。然后兩次合并最多需要3n-2次操作。它們是O(n)的。下一層遞歸調(diào)用2²次mergeSort，導(dǎo)致4次調(diào)用merge。每次調(diào)用merge最多3n/2²-1次操作合并n/2²項(xiàng)。四次合并，最多3n-2²次操作，也是O(n)的。

　　如果n是2^k的，則遞歸調(diào)用mergeSort方法的K層，導(dǎo)致進(jìn)行K層合并。每一層的合并都是O(n)的。因?yàn)閗是log₂n的，所以mergeSort是O(n log n)的。

　　注意：合并步驟是O(n)的，不管數(shù)組的初始狀態(tài)如何。最壞、最優(yōu)及平均情形下，歸并排序都是O(n log n)的。歸并排序的缺點(diǎn)是在合并階段需要一個(gè)臨時(shí)數(shù)組。

另一種評(píng)估效率的方法

　　遞推關(guān)系：t(n)表示最壞情形mergeSort的時(shí)間需求，則兩個(gè)遞歸調(diào)用的每個(gè)需要時(shí)間t(n/2)，合并步驟是O(n)，所以有

t(n) = t(n/2) + t(n/2) + O(n) = 2 x t(n/2) + O(n) ?????當(dāng)n > 1時(shí) t(1) = 0

設(shè)n猜想再證明

?

9.1.4 迭代歸并排序

　　為了使用迭代替代遞歸，我們需要控制合并過程。這樣一個(gè)算法不管是時(shí)間還是空間，都比遞歸算法更高效，因?yàn)樗诉f歸調(diào)用，所以去掉了活動(dòng)記錄的棧。但迭代歸并排序更難寫出沒有錯(cuò)誤的代碼。

　　基本上，迭代歸并排序從數(shù)組頭開始，將一對(duì)對(duì)的單項(xiàng)合并為含兩項(xiàng)的子段。然后返回到數(shù)組頭，將一對(duì)對(duì)的兩項(xiàng)的子段合并為4項(xiàng)的子段，以此類推。但是，合并某個(gè)長度的所有子段對(duì)后，可能還剩余若干項(xiàng)。合并這些項(xiàng)時(shí)需要格外小心。（可以節(jié)省很多將臨時(shí)數(shù)組復(fù)制回原始數(shù)組所需的時(shí)間）

?

9.1.5 Java類庫中的歸并排序

　　java.util包中的類Arrays定義了不同版本的幾個(gè)靜態(tài)方法sort，它們用來將數(shù)組按升序排序。對(duì)于對(duì)象數(shù)組，sort使用歸并排序。方法

public static void sort(Object[] a)

將對(duì)象數(shù)組a的全部內(nèi)容進(jìn)行排序，而方法

public static void sort(Object[] a, int first, int after)

對(duì)a[first]到a[after-1]之間的對(duì)象進(jìn)行排序。對(duì)于這兩個(gè)方法，數(shù)組中的對(duì)象必須定義了Comparable接口。

　　如果數(shù)組左半段中的項(xiàng)都不大于右半段中的項(xiàng)，則這些方法中使用的歸并排序會(huì)跳過合并步驟。因?yàn)閮啥硕家呀?jīng)有序，所以這種情形下合并步驟不是必需的。

　　注：穩(wěn)定的排序

如果排序算法不改變相等對(duì)象的相對(duì)次序，則稱為穩(wěn)定的（stable）。歸并排序是穩(wěn)定的。

?

9.2 快速排序

　　另一個(gè)使用分治策略的數(shù)組排序。快速排序（quick?sort）將數(shù)組劃分為兩部分，但與歸并排序不同，這兩部分不一定是數(shù)組的一半。相反，快速排序選擇數(shù)組中的一項(xiàng)（稱為樞軸（pivot））來重排數(shù)組項(xiàng)，滿足

1）?樞軸所處的位置就是在有序數(shù)組中的最終位置 2）?樞軸前的項(xiàng)都小于或等于樞軸 3）?樞軸后的項(xiàng)都大于或等于樞軸

這個(gè)排列稱為數(shù)組的劃分（partition）

　　創(chuàng)建劃分將數(shù)組分為兩部分，稱為較小部分和較大部分，它們由樞軸分開。因?yàn)檩^小部分中的項(xiàng)小于或等于樞軸，而較大部分中的項(xiàng)大于或等于樞軸，所以樞軸位于有序數(shù)組中正確且最終的位置上。現(xiàn)在如果對(duì)兩個(gè)子段的較小部分和較大部分進(jìn)行排序（當(dāng)然是用快速排序）則原始數(shù)組將是有序的。下列算法描述了排序策略：

Algorithm quicksort(a, first, last) // 遞歸地排序數(shù)組項(xiàng)a[first]到a[last] if (first < last){選擇樞軸基于樞軸劃分?jǐn)?shù)組pivotIndex = 樞軸的下標(biāo)quicksort(a, first, pivotIndex - 1) // 排序較小值部分quicksort(a, pivotIndex + 1, last) // 排序較大值的部分 }

9.2.1 快速排序的效率

　　注意，創(chuàng)建劃分（它完成了quickSort的大部分工作）在遞歸調(diào)用quickSort之前進(jìn)行。這一點(diǎn)與歸并排序不同，它的大部分工作是在遞歸調(diào)用mergeSort之后的合并步驟完成的。劃分過程需要不超過n次的比較，故與合并一樣，它將是O(n)的任務(wù)。

　　當(dāng)樞軸移動(dòng)到數(shù)組的中心時(shí)是理想情形，這樣劃分的兩個(gè)子數(shù)組有相同的大小。如果對(duì)quickSort的每次遞歸調(diào)用都劃分了相等大小的子數(shù)組，則快速排序與歸并排序一樣遞歸調(diào)用數(shù)組的兩半。所以快速排序?qū)⑹荗(n log n)的，這是最優(yōu)情形。

　　最壞情形下，每次劃分都有一個(gè)空子段，另一個(gè)調(diào)用必須排序n-1項(xiàng)。結(jié)果是n層遞歸調(diào)用而不是log n層。所以最壞情形下，快速排序是O(n²)的。

　　樞軸的選擇將影響快速排序的效率。如果數(shù)組已經(jīng)有序或接近有序，有些選擇樞軸的機(jī)制可以導(dǎo)致最壞情形。實(shí)際上，出現(xiàn)接近有序數(shù)組的情形，可能會(huì)更頻繁。

快速排序在平均情形下是O(n log n)的，歸并排序總是O(n log n)的，而實(shí)際上，快速排序可能比歸并排序更快，且不需要?dú)w并排序中合并操作所需的額外內(nèi)存。

?

9.2.2 創(chuàng)建劃分

　　樞軸與最后一項(xiàng)交換。

等于樞軸的項(xiàng)

　　注意，在較小部分和較大部分子數(shù)組中，都可能含有等于樞軸的項(xiàng)。為什么不總是將等于樞軸的項(xiàng)放到同一個(gè)子段中呢？這樣的策略能讓一個(gè)子段大于另一個(gè)。但是，為了提升快速排序的性能，讓子數(shù)組盡可能地等長。

　　注意，從左至右的查找和從右至左的查找，在它們遇到等于樞軸的項(xiàng)時(shí)都會(huì)停止。這意味著，這樣的項(xiàng)不是放在原地，而是要進(jìn)行交換。也意味著，這樣的項(xiàng)有機(jī)會(huì)放在任何一個(gè)子數(shù)組中。

樞軸的選擇

　　理想地，樞軸應(yīng)該是數(shù)組的中位值，所以較小部分和較大部分子數(shù)組都有相等（或接近相等）的項(xiàng)數(shù)。找到中位值的一種方法是排序數(shù)組，然后選擇位于中間的值，但數(shù)組排序是原始問題，所以這個(gè)思路不行。

　　選擇樞軸需要不花太多時(shí)間，所以至少應(yīng)該避開壞的樞軸。所以不是去找數(shù)組的中位值，而是找到數(shù)組中這3個(gè)項(xiàng)的中位值：第一項(xiàng)、中間項(xiàng)及最后一項(xiàng)。一個(gè)辦法是僅將這3個(gè)值進(jìn)行排序，使用這3個(gè)值的中間值作為樞軸。這個(gè)選擇策略稱為三元中值樞軸選擇（median-of-three pivot selection）。

　　注：三元中值樞軸選擇避免了快速排序當(dāng)給定數(shù)組已經(jīng)有序或接近有序時(shí)的最壞情形性能。但理論上，不能避免其他情況下數(shù)組的最壞性能，這樣的性能在實(shí)際中不太可能出現(xiàn)。

修改劃分算法

　　三元中值樞軸選擇說明，對(duì)劃分機(jī)制要做小的修改。之前樞軸與數(shù)組最后一項(xiàng)交換，因?yàn)楝F(xiàn)在已知最后一項(xiàng)至少大于等于樞軸，所以最后一項(xiàng)不動(dòng)，將樞軸與倒數(shù)第二項(xiàng)交換。所以，劃分算法從下標(biāo)last –?2處開始從右至左的查找。

　　同樣，第一項(xiàng)直多等于樞軸，所以也不動(dòng)，劃分算法從下標(biāo)first+1開始從左至右的查找。

　　這個(gè)機(jī)制使得進(jìn)行兩個(gè)查找的循環(huán)簡單了。從左至右的查找查看大于等于樞軸的項(xiàng)。這個(gè)查找將會(huì)停止，因?yàn)樗辽贂?huì)停在樞軸處，從右至左的查找查看小于或等于樞軸的項(xiàng)。這個(gè)查找將會(huì)停止，因?yàn)橹辽贂?huì)停在第一項(xiàng)。所以循環(huán)不需要為阻止查找越出數(shù)組邊界而做什么特殊的事情。

　　查找循環(huán)停止后，必須將樞軸放到較小部分和較大部分的中間。通過交換a[indexFromLeft]和a[last - 1]處的項(xiàng)可做到這一點(diǎn)。

　　注：快速排序在劃分過程中重排數(shù)組中的項(xiàng)。每次劃分都將一個(gè)項(xiàng)（樞軸）放在其正確的有序位置。在兩個(gè)子數(shù)組中位于樞軸之前和之后的項(xiàng)仍留在各自的子數(shù)組中。

?

9.2.3 實(shí)現(xiàn)快速排序

樞軸的選擇

　　可以通過私有方法，簡單的比較及交換完成第一項(xiàng)、中間項(xiàng)、最后一項(xiàng)的比較。

// Sorts the first, middle, and last entries of an array into ascending order. private static <T extends Comparable<? super T>> void sortFirstMiddleLast(T[] a, int first, int mid, int last)

劃分

　　若數(shù)組小于三項(xiàng)，則已經(jīng)排好，所以不需要?jiǎng)澐只蚩炫?#xff0c;所以下列劃分算法假設(shè)數(shù)組至少有四項(xiàng)：

Algorithm partition (a, first, last) // 作為快速排序的一部分，劃分將數(shù)組a[first...last]分為兩個(gè)子數(shù)組 // 分別稱為Smaller 和 Larger，它由一個(gè)項(xiàng)（樞軸），名為pivoValue，分隔開。 // Smaller 中的項(xiàng) ≤ pivotValue, 且位于數(shù)組中pivotValue 值的前面 // Larger 中的項(xiàng) ≥ pivotValue, 且位于數(shù)組中pivotValue 值的后面 // first >= 0; first < a.length; last - first >= 3; last < a.length // 返回樞軸的下標(biāo)
mid = 數(shù)組中間項(xiàng)的下標(biāo) sortFirstMiddleLast(a, first, mid, last) // 斷言：a[first] <= pivotValue 且 a[last] >= pivotValue, 所以數(shù)組的這兩項(xiàng)不與pivotValue進(jìn)行比較 // 將 pivotValue移到數(shù)組中倒數(shù)第二個(gè)位置 交換 a[mid] 和a[last - 1] pivotIndex = last - 1 pivotValue = a[pivotIndex]
// 判斷兩個(gè)子數(shù)組: // Smaller = a[first...endSamller] 且 // Larger = a[endSmaller+1...last-1] // 這樣，Smaller 中的項(xiàng)都 <= pivotValue, 且 // Larger 中的項(xiàng)都 >= pivotValue // 初始時(shí)，這些子數(shù)組都是空的 indexFromLeft = first + 1 indexFromRight = last - 2 done = false while (!done) { // 從數(shù)組頭開始，留下 < pivotValue 的項(xiàng)， // 找到 >= pivotValue 的第一個(gè)項(xiàng)。一定能找到一個(gè)， // 因?yàn)樽詈笠豁?xiàng) >= pivotValue while (a[indexFromLeft] < pivotValue) indexFromLeft++
// 從數(shù)組尾開始，留下 > pivotValue 的項(xiàng)， // 找到 <= pivotValue 的第一個(gè)項(xiàng) // 一定能找到一個(gè)，因?yàn)榈谝粋€(gè)項(xiàng) <= pivotValue while (a[indexFromRight] > pivotValue) indexFromRight--
// 斷言：a[indexFromLeft] >= pivotValue 且 // a[indexFromRight] <= pivotValue if (indexFromRight > indexFromLeft) {交換 a[indexFromLeft] 和 a[indexFromRight]indexFromLeft++indexFromRight-- } elsedone = true } // 將 pivotValue 放到子數(shù)組 Smaller 和 Larger 之間 交換 a[pivotIndex] 和 [indexFromLeft] pivotIndex = indexFromLeft // 斷言：Smaller = a[first...pivotIndex-1] // pivotValue = a[pivotIndex] // Larger = a[pivotIndex+1...last] return pivotIndex

快速排序方法

　　即使是對(duì)大數(shù)組進(jìn)行劃分，最終也會(huì)導(dǎo)致遞歸調(diào)用時(shí)涉及僅有兩項(xiàng)的小數(shù)組。快速排序的代碼必須篩選出這些小數(shù)組，并使用其他方法來排序它們。插入排序是小數(shù)組的好選擇。實(shí)際上，對(duì)于含10項(xiàng)的數(shù)組，使用插入排序替代快速排序都是合理的。實(shí)現(xiàn)如下：

/*** Sorts an array into ascending order. Uses quick sort with* median-of-three pivot selection for arrays of at least* MIN_SIZE entries, and uses insertion sort for smaller arrays.*/ public static <T extends Cpmaprble<? super T>> void quickSort(T[] a, int first, int last) {if (last - first + 1 < MIN_SIZE) {insertionSort(a, first, last)}else {// Create the partition: Smaller | pivot | Largerint pivotIndex = partition(a, first, last);// Sort subarrays Smaller and LargerquickSort(a, first, pivotIndex - 1);quickSort(a, pivotIndex + 1, last);} // end if } // end quickSort

?

9.2.4?Java類庫中的快速排序?

　　包Java.util中的類Array使用快速排序?qū)绢愋偷臄?shù)組進(jìn)行升序排序。方法

public static void sort(type[] a)

對(duì)整個(gè)數(shù)組a進(jìn)行排序，而方法?

public static void sort(type[] a, int first, int after)

對(duì)從a[first]?到a[after-1]的項(xiàng)進(jìn)行排序。注意，type可以是byte、char、double、float、int、long 或 short 類型。

?

9.3 基數(shù)排序

　　到目前為止，這些排序算法對(duì)可比較的對(duì)象進(jìn)行排序。基數(shù)排序（radix sort）不使用比較，但為了能進(jìn)行排序，它必須限制排序的數(shù)據(jù)。對(duì)于這些受限的數(shù)據(jù)，基數(shù)排序是O(n)的，故它快于之前的任何一種排序方法。但是，它不適合作為通用的排序算法，因?yàn)樗鼘?shù)組項(xiàng)看做有相同長度的字符串。

　　基數(shù)排序需要相同的長度，不足的前面補(bǔ)0（對(duì)于數(shù)字來說），先按照最后一位比較，再按照倒數(shù)第二位比較，以此類推，最后用第一位比較，過程如下：

　　對(duì)10個(gè)數(shù)進(jìn)行排序：123,?398,?210,?019,?528,?003,?513,?129,?220,?294

先按最右邊的數(shù)字分組，將123放入3號(hào)桶，210放入0號(hào)桶，放完再移回?cái)?shù)組，再按照中間數(shù)組分桶。

?

?

9.3.1 基數(shù)排序的偽代碼

　　下列算法描述了對(duì)正的十進(jìn)制整數(shù)數(shù)組的基數(shù)排序。從0開始對(duì)每個(gè)整數(shù)從右到左標(biāo)記各位。所以，個(gè)位數(shù)字是數(shù)字0，十位數(shù)字是數(shù)字1，以此類推。

Algorithm radixSort(a, first, last, maxDigits) // 升序排序十進(jìn)制正整數(shù)數(shù)組a[first…last]; // maxDigits 是最長整數(shù)的數(shù)字位數(shù) for (i = 0 to maxDigits - 1){清空 bucket[0], bucket[1],…, bucket[9]for (index = first to last){digit = digit I of a[index]將 a[index] 放到 bucket[digit] 的最后 } 將 bucket[0], bucket[1], …, bucket[9] 放回?cái)?shù)組a 中 }

算法用到了桶的數(shù)組。沒有指定桶的特性。

?

9.3.2 基數(shù)排序的效率

　　如果數(shù)組含有n個(gè)整數(shù)，則前一個(gè)算法中的內(nèi)層循環(huán)迭代n次。如果每個(gè)整數(shù)含有d位，則外層循環(huán)迭代d次。所以基數(shù)排序是O(d x n)的。表達(dá)式中的d說明，基數(shù)排序的實(shí)際運(yùn)行時(shí)間依賴于整數(shù)的大小。但在計(jì)算機(jī)中，一般的整數(shù)最大不超過10位十進(jìn)制數(shù)，或32個(gè)二進(jìn)制位。當(dāng)d固定且遠(yuǎn)小于n時(shí)，基數(shù)排序僅僅是O(n)的算法。

　　注：雖然基數(shù)排序?qū)δ承?shù)據(jù)是O(n)的算法，但它不適用于所有數(shù)據(jù)。

?

9.4 算法比較

　　雖然基數(shù)排序是最快的，但它并不總能使用。一般來說歸并排序和快速排序比其他算法快。如果數(shù)組含有相對(duì)較少的項(xiàng)，或者如果接近有序，則插入排序是好的選擇。另外，一般來講快速排序是可取的。注意，當(dāng)數(shù)據(jù)集合（collection）太大，不能全部放到內(nèi)存而必須使用外部文件時(shí)，可以使用歸并排序。另一個(gè)排序——堆排序，也是O(n log n)的，但快排更可取。

?	平均情形	最優(yōu)情形	最壞情形
基數(shù)排序	O(n)	O(n)	O(n)
歸并排序	O(n log n)	O(n log n)	O(n log n)
快速排序	O(n log n)	O(n log n)	O(n2)
希爾排序	O(n1.5)	O(n)	O(n2)或O(n1.5)
插入排序	O(n2)	O(n)	O(n2)
選擇排序	O(n2)	O(n2)	O(n2)

對(duì)比各增長速度

n	10	102	103	104	105	106
n log2?n	33	664	9966	132877	1660964	19931569
n1.5	32	103	31623	106	31622777	109
n2	102	104	106	108	1010	1012

?

小結(jié)

1）?歸并排序是分治算法，它將數(shù)組分半，遞歸地排序兩半，然后將它們合并為一個(gè)有序數(shù)組 2）?歸并排序是O(n log n)的。但是它需要用到額外的內(nèi)存來完成合并過程 3）?快速排序是另一種分治算法，它由一項(xiàng)（樞軸）將數(shù)組劃分為分開的兩個(gè)子數(shù)組。樞軸在其正確的有序位置上。一個(gè)子數(shù)組中的項(xiàng)小于或等于樞軸，而第二個(gè)子數(shù)組中的項(xiàng)則大于或等于樞軸。快速排序遞歸的對(duì)兩個(gè)子數(shù)組進(jìn)行排序 4）?大多數(shù)情況下，快速排序是O(n log n)的。雖然最壞的情況下是O(n2)的，但通常選擇合適的樞軸可以避免這種情況 5）?即使歸并排序和快速排序都是O(n log n)的算法，但在實(shí)際中，快速排序通常更快，且不需要額外的內(nèi)存 6）?基數(shù)排序?qū)?shù)組項(xiàng)看做有相同長度的字符串。初始時(shí)，基數(shù)排序根據(jù)字符串一端的字符（數(shù)字）將項(xiàng)分配到桶中，然后排序收集字符串，并根據(jù)下一個(gè)位置的字符或數(shù)字將它們?cè)俅畏峙涞酵爸小＠^續(xù)這個(gè)過程，直到所有的字符位置都處理過為止 7）?基數(shù)排序不對(duì)數(shù)組項(xiàng)進(jìn)行比較。雖然它是O(n)的，但它不能對(duì)所有類型的數(shù)據(jù)進(jìn)行排序。所以它不能用作通用的排序算法。

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/datamining-bio/p/9686283.html

總結(jié)

以上是生活随笔為你收集整理的（十）更快的排序算法（归并、快排、基数）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。