第9章-綜合比較解讀

第9章內(nèi)部排序9.1排序的基本概念9.2插入類排序9.3交換類排序法9.4選擇類排序法9.5歸并排序9.6安排類排序9.7各種排序方法的綜合比較9.8總結(jié)與提高9.7各種排序方法的綜合比較首先從算法的平均時(shí)間困難度、最壞時(shí)間困難度、以及算法所需的協(xié)助存儲(chǔ)空間三方面，對(duì)各種排序方法加以比較。排序方法平均時(shí)間復(fù)雜度最壞時(shí)間復(fù)雜度輔助存儲(chǔ)空間簡(jiǎn)單排序O(n2)O(n2)O(1)快速排序O(nlogn)O(n2)O(logn)堆排序O(nlogn)O(nlogn)O(1)歸并排序O(nlogn)O(nlogn)O(n)各種排序方法的性能比較通過(guò)分析和比較，可以得出以下結(jié)論：簡(jiǎn)潔排序一般只用于n值較小的狀況；歸并排序適用于n值較大的狀況；快速排序是排序方法中最好的方法。從排序的穩(wěn)定性來(lái)看，基數(shù)排序是穩(wěn)定的，除了簡(jiǎn)潔選擇排序，其它各種簡(jiǎn)潔排序法也是穩(wěn)定的。多數(shù)狀況下，排序是按記錄的主關(guān)鍵字進(jìn)行的，此時(shí)不用考慮排序方法的穩(wěn)定性。假如排序是按記錄的次關(guān)鍵字進(jìn)行的，則應(yīng)充分考慮排序方法的穩(wěn)定性。9.8總結(jié)與提高9.8.1主要學(xué)問(wèn)點(diǎn)1.本章共介紹了插入、交換、選擇、、歸并、安排這5類內(nèi)排序算法，均為基于比較的排序，即排序過(guò)程的實(shí)現(xiàn)主要靠關(guān)鍵字的關(guān)系大小比較。理解各類排序的基本方法特別重要。2.嫻熟駕馭三種簡(jiǎn)潔排序方法（干脆插入、冒泡排序、簡(jiǎn)潔選擇）的基本思想和算法描述,駕馭這些排序法的特點(diǎn)和適用狀況，并能應(yīng)用分析。3.駕馭三種改進(jìn)排序方法（希爾排序、快速排序、堆排序）的基本思路,駕馭這些排序法的特點(diǎn)和適用狀況，并能依據(jù)特點(diǎn)給出應(yīng)用分析。4.理解歸并排序法的基本思想和算法描述。5.駕馭基數(shù)排序法基本思想和兩種實(shí)現(xiàn)途徑。6.證明一種排序方法是穩(wěn)定的，要從算法本身的步驟中加以證明。證明排序方法是不穩(wěn)定的，只需給出一個(gè)反例說(shuō)明。9.8.2典型題例例1：排序方法選擇①設(shè)有10000個(gè)無(wú)序元素，僅要求找出前10個(gè)最小元素，在下列排序方法中（歸并排序、基數(shù)排序、快速排序、堆排序、插入排序）哪一種方法最好，為什么？解：待排序元素1萬(wàn)，僅需找出前10個(gè)最小元素，因此并不須要整個(gè)排序；在所給定的方法中，調(diào)用堆排序中的一趟排序，即可通過(guò)最小堆找出一個(gè)最小值，每趟排序只需僅需10次調(diào)用一趟排序，即可達(dá)到要求結(jié)果。而其他的歸并排序、基數(shù)排序、快速排序、插入排序方法均要全部排好才可達(dá)到要求,因此選擇堆排序最好。②對(duì)長(zhǎng)度為n的記錄序列進(jìn)行快速排序時(shí)，所需進(jìn)行的比較次數(shù)依靠于這n個(gè)元素的初始排列。分析其最壞與最好狀況，對(duì)n=7給出一個(gè)最好狀況的初始排列實(shí)例。解：快速排序算法是平均排序性能最好的算法之一?？焖倥判蜃顗臓顩r是序列有序，每次以樞軸元素為界，序列分為兩個(gè)子表，一個(gè)子表為空，另一個(gè)子表為n-1個(gè)元素，快速排序蛻變?yōu)槊芭菖判?。快速排序最好狀況是這樣的排列，每次的樞軸元素放置的位置在表中間，正好能夠?qū)⑿蛄蟹譃閮蓚€(gè)長(zhǎng)度相當(dāng)?shù)淖颖?，此時(shí)快速排序性能類同折半判定樹的分析。其趟數(shù)為log2n」+1。②對(duì)長(zhǎng)度為n的記錄序列進(jìn)行快速排序時(shí)，所需進(jìn)行的比較次數(shù)依靠于這n個(gè)元素的初始排列。分析其最壞與最好狀況，對(duì)n=7給出一個(gè)最好狀況的初始排列實(shí)例。n=7時(shí)一個(gè)最好狀況的初始排列實(shí)例為：[4，1，3，2，6，5，7]第一趟劃分結(jié)果為：[2，1，3]