總結(jié)和習(xí)題習(xí)題課各種排序方法的比較本章的主要內(nèi)部排序方法.本章的主要內(nèi)部排序方法本章研究的內(nèi)部排序方法主要有：插入排序直接插入排序希爾排序交換類排序起泡排序快速排序選擇類排序簡(jiǎn)單選擇排序堆排序歸并排序基數(shù)排序多關(guān)鍵字排序鏈?zhǔn)交鶖?shù)排序.1.插入排序

1)基本思想：插入排序：將無序子序列中的一個(gè)或幾個(gè)記錄“插入”到有序序列中，從而增加記錄的有序子序列的長(zhǎng)度。本章的主要排序方法.2)常見的插入排序算法

a.直接插入排序（基于順序查找）b.希爾排序（基于逐趟縮小增量）O(n2)是一種穩(wěn)定的排序方法是一種不穩(wěn)定的排序方法本章的主要排序方法.2.交換類排序

1)基本思想：依次兩兩比較相鄰關(guān)鍵字，并交換不滿足排序要求的關(guān)鍵字，直至全部有序。本章的主要排序方法.2)常見的交換類排序算法

a.起泡排序b.快速排序O(n2)是一種穩(wěn)定的排序方法是一種不穩(wěn)定的排序方法O(nlogn)本章的主要排序方法.3.選擇類排序

1)基本思想：每一趟從待排序的n-i+1（i=1,2,3,…,n-1）個(gè)記錄中選出關(guān)鍵字最小的記錄，作為有序序列中第i個(gè)記錄，直到全部記錄排序完畢。本章的主要內(nèi)部排序方法.2)常見的選擇類排序算法

O(n2)是一種不穩(wěn)定的排序方法是一種不穩(wěn)定的排序方法O(nlogn)a.簡(jiǎn)單選擇排序b.堆選擇排序本章的主要內(nèi)部排序方法.4.歸并排序

1)基本思想：將兩個(gè)或兩個(gè)以上的有序子序列“歸并”為一個(gè)有序序列。時(shí)間復(fù)雜度為Ο(nlogn)。是一種穩(wěn)定的排序方法本章的主要內(nèi)部排序方法.各種內(nèi)部排序方法的比較5.鏈?zhǔn)交鶖?shù)排序

1)基本思想：在多關(guān)鍵字的記錄序列中，每個(gè)關(guān)鍵字的取值范圍相同，則按LSD法進(jìn)行排序時(shí)，可以采用“分配-收集”的方法，不需要進(jìn)行關(guān)鍵字間的比較。時(shí)間復(fù)雜度為O(d(n+rd))是穩(wěn)定的排序方法.各種內(nèi)部排序方法的比較1.平均的時(shí)間性能基數(shù)排序①時(shí)間復(fù)雜度為O(nlogn)：快速排序、堆排序和歸并排序②時(shí)間復(fù)雜度為O(n2)：直接插入排序、起泡排序和簡(jiǎn)單選擇排序③時(shí)間復(fù)雜度為O(d(n+rd)):一、時(shí)間性能.各種內(nèi)部排序方法的比較2.當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí)①直接插入排序和起泡排序能達(dá)到O(n)的時(shí)間復(fù)雜度②快速排序的時(shí)間性能蛻化為O(n2)。3.簡(jiǎn)單選擇排序、堆排序和歸并排序的時(shí)間性能不隨記錄序列中關(guān)鍵字的分布而改變。.各種內(nèi)部排序方法的比較二、空間性能指的是排序過程中所需的輔助空間大小1.

所有的簡(jiǎn)單排序方法(包括：直接插入、起泡和簡(jiǎn)單選擇)和堆排序的空間復(fù)雜度為O(1)；2.

快速排序?yàn)镺(logn)，為遞歸程序執(zhí)行過程中，棧所需的輔助空間；.各種內(nèi)部排序方法的比較3.

歸并排序所需輔助空間最多，其空間復(fù)雜度為O(n);4.鏈?zhǔn)交鶖?shù)排序需附設(shè)隊(duì)列首尾指針，則空間復(fù)雜度為O(rd)。.各種內(nèi)部排序方法的比較三、排序方法的穩(wěn)定性能1.穩(wěn)定的排序方法指的是，對(duì)于兩個(gè)關(guān)鍵字相等的記錄，它們?cè)谛蛄兄械南鄬?duì)位置，在排序之前和經(jīng)過排序之后，沒有改變。排序之前:{·····Ri(K)·····Rj(K)·····}排序之后:{·····Ri(K)Rj(K)··········}.各種內(nèi)部排序方法的比較2.

當(dāng)對(duì)多關(guān)鍵字的記錄序列進(jìn)行LSD方法排序時(shí)，必須采用穩(wěn)定的排序方法。3.對(duì)于不穩(wěn)定的排序方法，只要能舉出一個(gè)實(shí)例說明即可。4.快速排序、堆排序和希爾排序是不穩(wěn)定的排序方法。例如:對(duì){4,3,4,2}進(jìn)行快速排序，得到{2,3,4,4}.各種內(nèi)部排序方法的比較四、關(guān)于“排序方法的時(shí)間復(fù)雜度的下限”本章討論的各種排序方法，除基數(shù)排序外，其它方法都是基于“比較關(guān)鍵字”進(jìn)行排序的排序方法。可以證明，這類排序法可能達(dá)到的最快的時(shí)間復(fù)雜度為O(nlogn)。(基數(shù)排序不是基于“比較關(guān)鍵字”的排序方法，所以它不受這個(gè)限制。).各種內(nèi)部排序方法的比較

例如:對(duì)三個(gè)關(guān)鍵字進(jìn)行排序的判定樹如下：K1<K3K1<K2K1<K3K2<K3K2<K3K2<K1<K3K1<K2<K3K3<K2<K1K2<K3<K1K3<K1<K2K1<K3<K2１．樹上的每一次“比較”都是必要的;２．樹上的葉子結(jié)點(diǎn)包含所有可能情況。.各種內(nèi)部排序方法的比較一般情況下，對(duì)n個(gè)關(guān)鍵字進(jìn)行排序，可能得到的結(jié)果有n!

種，由于含n!

個(gè)葉子結(jié)點(diǎn)的二叉樹的深度不小于log2(n!)+1,則對(duì)n個(gè)關(guān)鍵字進(jìn)行排序的比較次數(shù)至少是log2(n!)

nlog2n(斯蒂林近似公式)。所以，基于“比較關(guān)鍵字”進(jìn)行排序的排序方法，可能達(dá)到的最快的時(shí)間復(fù)雜度為O(nlogn)。.1、在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）

A插入排序B選擇排序C快速排序D歸并排序2、在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排序次序無關(guān)的是（）

A起泡排序B希爾排序C插入排序D選擇排序【答案】A【答案】D習(xí)題課.3、排序方法中，從未排序隊(duì)列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，然后放入到已排序序列中的正確位置上，這種方法稱為（）

A起泡排序B選擇排序C插入排序D堆排序4、下列排序方法中，（）是從未排序序列中依次挑選元素，并將其放入已排序序列（初始為空）的末尾。

A希爾排序B歸并排序C選擇排序D插入排序【答案】C【答案】C習(xí)題課.5、對(duì)n個(gè)記錄進(jìn)行堆排序，最壞情況下的執(zhí)行時(shí)間為

A)O(log2n)B)O(n)C)O(nlog2n)D)O(n2)6、用直接插入排序方法對(duì)下面四個(gè)序列進(jìn)行排序（由小到大），元素比較次數(shù)最少的是

A）94、32、40、90、80、46、21、69B）32、40、21、46、69、94、90、80

C）21、32、46、40、80、69、90、94D）90、69、80、46、21、32、94、40【答案】C【答案】C習(xí)題課.7、用快速排序法對(duì)包含n個(gè)關(guān)鍵字的序列進(jìn)行排序，最壞情況下的執(zhí)行時(shí)間為

A）O(log2n)B）O(n)C）O(nlog2n)D）O(n2)【答案】D習(xí)題課8、下列哪一個(gè)關(guān)鍵碼序列不符合堆的定義？

A）A、C、D、G、H、M、P、Q、R、X

B）A、C、M、D、H、P、X、G、O、R

C）A、D、P、R、C、Q、X、M、H、G

D）A、D、C、M、P、G、H、X、R、Q【答案】C.9、已知一個(gè)序列為{21，39，35，12，17，43}，則利用堆排序的方法建立的初始堆為（）

A39，21，35，12，17，43B43，39，35，12，17，21C43，39，35，21，17，12D43，35，39，17，21，12【答案】B習(xí)題課10、一組記錄的關(guān)鍵字為{46，79，50，38，42，80}，利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為

A38，42，46，50，79，80B42，38，46，79，50，80C42，38，46，79，80，50D42，38，46，80，50，76【答案】C

.11、用某種排序方法對(duì)線性表（25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，元素序列的變化情況如下：（1）25，84，21，47，15，27，68，35，20（2）20，15，21，25，47，27，68，35，84（3）15，20，21，25，35，27，47，68，84（4）15，20，21，25，27，35，47，68，84則所采用的排序方法是（）

A選擇排序B快速排序C歸并排序D希爾排序12、在插入排序、希爾排序、選擇排序、堆排序、快速排序、歸并排序中，排序穩(wěn)定的有————————————?！敬鸢浮緽插入排序、歸并排序習(xí)題課.13、已知如下代碼:

FORi=2TOnDO{

x=A[i];j=i-1;

WHILE(j>0)AND(A[j]>x)DO{

A[j+1]:=A[j];

j:=j-1

}A[j+1]=x

}

1、這段代碼所描述的排序方法是____________。2、這段代碼所描述的排序方法的時(shí)間復(fù)雜度為______。

3、假設(shè)這段代碼開始執(zhí)行時(shí),數(shù)組A中的元素已經(jīng)按值的遞增次序排好了序,則這段代碼的執(zhí)行時(shí)間為____________。直接插入排序O(n2)O(n)

習(xí)題課.14、設(shè)有n個(gè)無序元素，按非遞減次序排序，但只想得到前面長(zhǎng)度為k的部分序列，其中n>>k，最好采用什么排序方法？為什么？如果有這樣的一個(gè)序列{59，11，26，34，17，91，25}，得到的部分序列是{11，17，25}，對(duì)于該例使用所選擇的方法實(shí)現(xiàn)時(shí)，共執(zhí)行多少次比較？習(xí)題課15、給出如下關(guān)鍵字