第7章排序算法

i.請簡述排序的作用。

排序的作用是將一個待排序元素集合按關(guān)鍵字遞增(或遞減)順

序整理為一個有序序列。

2.請簡述穩(wěn)定排序和不穩(wěn)定排序的含義。

若采用某種排序算法對任一組元素進(jìn)行排序，在排序前后，那些

具有相同關(guān)鍵字值的元素之間的相對次序都保持不變，則將這種排序

算法稱為是穩(wěn)定的，否則稱為是不穩(wěn)定的。

3.請簡述各種排序算法的適用范圍。

排序算法的適用范圍如下：

(a)直接插入排序'簡單選擇排序和冒泡排序都是簡單排序算

法，它們的時間復(fù)雜度和空間復(fù)雜度分別為。(吊)和0(1)。若待排序

元素數(shù)量n較小，可以選用直接插入排序和冒泡排序。另外，當(dāng)待排

序元素基本有序時，也應(yīng)選用直接插入排序和冒泡排序，此時時間復(fù)

雜度都能達(dá)到O(n)。若元素本身數(shù)據(jù)量較大,元素移動操作代價較高,

則應(yīng)選用平均移動元素次數(shù)最少的簡單選擇排序。希爾排序是對直接

插入排序算法的改進(jìn)，大大降低了時間復(fù)雜度，但它是一種不穩(wěn)定的

排序算法。

(b)堆排序'快速排序和歸并排序主要適用于待排序元素數(shù)量

n較大的情況，當(dāng)待排序元素數(shù)量n較小時，它們的性能有可能劣于

簡單排序算法。因此，在實際應(yīng)用時，快速排序算法和歸并排序算法

經(jīng)常與簡單排序算法結(jié)合使用（例如，可以先用快速排序算法將集合

劃分為規(guī)模更小的子集合，對于元素數(shù)量較小的子集合，則用直接插

入排序算法進(jìn)行排序）。在所有平均時間復(fù)雜度為O（nlog2n）的算法

中，盡管快速排序在最壞情況下時間復(fù)雜度較高，但它通常被認(rèn)為是

平均性能最好的一種算法，并且通過優(yōu)化可以降低最壞情況出現(xiàn)的概

率。歸并排序是一種穩(wěn)定的排序算法，其時間性能一般要優(yōu)于堆排序,

但它所需要的輔助空間較多，當(dāng)應(yīng)用環(huán)境要求排序前后具有相同值的

元素相對次序不能改變時可以考慮使用。堆排序所需的輔助空間最

少，當(dāng)可用空間非常有限時可以考慮使用。

（c）箱排序和基數(shù)排序的時間復(fù)雜度最低，但它們的空間復(fù)雜

度最高。箱排序主要適用于待排序元素長度（即d值）較小的情況，

在實際中應(yīng)用不多；基數(shù)排序是箱排序的改進(jìn)，主要適用于整數(shù)或字

符串的排序，或者與其他排序算法結(jié)合進(jìn)行實數(shù)的排序（例如，可以

先用基數(shù)排序算法按整數(shù)部分將元素分成若干個子集合，再對每個子

集合應(yīng)用直接插入排序算法進(jìn)行排序）。

4.請簡述插入排序、選擇排序、交換排序、歸并排序和分配排

序的原理。

插入排序：按關(guān)鍵字大小每次將一個待排序的元素插入到已排序

的序列中，直至所有元素都插入完畢。

選擇排序：每次從待排序的元素中選擇具有最小（或最大）關(guān)鍵

字的元素放到已排序序列的尾部（或頭部），直至所有元素都排序完

畢。

交換排序：從待排序的元素中選擇兩個次序相反的元素進(jìn)行交

換，直至任意兩個元素的次序都正確。

K路歸并排序：每次將K(KN2)個已排序的子序列組合在一起,

形成一個有序的序列，重復(fù)該過程直至得到一個包含所有待排序元素

的有序序列。

分配排序：根據(jù)元素本身所具有的值將各元素逐一映射到一組有

序空間中，最后再依次從有序空間中將各元素取出即形成了排序結(jié)

果。

5.請簡述直接插入排序的具體步驟。

直接插入排序是一種簡單排序算法，其具體步驟為：

(a)初始已排序區(qū)為空，將第一個待排序的元素插入到已排序

區(qū)中。

(b)將后繼每一個待排序的元素依次取出，并按照關(guān)鍵字大小

將其插入到已排序區(qū)中的適當(dāng)位置，使該序列仍然有序。

(c)重復(fù)上一步驟直至將待排序的元素都插入到已排序序列中o

6.請簡述希爾排序的具體步驟。

希爾排序，又稱為“縮小增量排序”，其具體步驟為：

(a)令n為待排序元素數(shù)目，設(shè)置增量序列{do,di,…，dk},其

中n>do>di>...>dk=lo

(b)按增量&(i依次取值為0,1,k)將待排序元素分為&

組，將所有下標(biāo)距離為&的倍數(shù)的元素放在同一組中，即R[1],R[1+

di],R[l+2*&],...在第一組中,R[2],R[2+di],R[2+2*di],……在第二組

中，……，依此類推。然后分別在各組內(nèi)進(jìn)行直接插入排序。

(C)重復(fù)上一步驟直至最后以1為增量對所有待排序元素進(jìn)行

直接插入排序。

7.請簡述簡單選擇排序的具體步驟。

簡單選擇排序是一種簡單排序算法，其具體步驟為：

(a)初始已排序區(qū)為空，待排序區(qū)包含所有待排序元素。

(b)從待排序區(qū)中選擇具有最小關(guān)鍵字的元素，將其與待排序

區(qū)的第一個元素交換位置，并將該位置加到已排序區(qū)中。

(c)重復(fù)上一步驟直至所有元素都排序完畢。

8.請簡述堆的定義和堆的構(gòu)建過程。

堆的定義：

對于包含n個元素的集合R={R[1],R[2],R[n]},若滿足：

(1)R[i]0R[2*i]且R[i]SR[2*i+l](即R所表示的完全二叉樹中

每一棵子樹的根結(jié)點的值均不大于其孩子結(jié)點的值)。

(2)或R[i]NR[2*i]且R[i]NR[2*i+l](即R所表示的完全二叉樹

中每一棵子樹的根結(jié)點的值均不小于其孩子結(jié)點的值)。

則稱集合R為堆。若滿足前一個條件則稱R為小根堆，滿足后

一個條件則稱R為大根堆。

堆的構(gòu)建過程：

堆一般采用自底向上的構(gòu)建方法，即在將以某一結(jié)點為根結(jié)點的

二叉樹構(gòu)建成堆之前，先將其左子樹和右子樹構(gòu)建成堆。以葉子結(jié)點

為根的子樹必然是堆，因此，對于由n個元素構(gòu)成的完全二叉樹，其

對應(yīng)的堆的構(gòu)建過程從R[l_n/2」]作為根結(jié)點的子樹開始，依次對

R[Ln/2j-l]vR[|_n/2」-2]、…、R[l]作為根結(jié)點的樹進(jìn)行堆的構(gòu)建。

在將一棵R[i]作為根結(jié)點的子樹整理為堆時，只有根結(jié)點不滿足

堆的條件，因此，需將根結(jié)點與后繼層中的結(jié)點依次比較并不斷將根

結(jié)點下移直至該子樹滿足堆的條件，這里以大根堆構(gòu)建為例介紹其具

體過程：

(a)若R[i]存在左孩子R[2*i],則令j=2巧;若R[i]存在右孩子

R[2*i+1]且R[2*i+l]>R[2*i],則令j=2*i+l。將R|j]與R國比較,若

R[i]較小，則將R[i]和R[j]交換,并令i=j。

(b)重復(fù)上述步驟直至R[i]無孩子結(jié)點或R[i]比其孩子結(jié)點都

大，此時該子樹即為堆。

9.請簡述堆排序的具體步驟。

堆排序的具體過程：

(a)采用自底向上的方法將包含n個元素的待排序集合R={R[1],

R[2],…,R[n]}整理為大根堆，其元素數(shù)目i=n,初始時已排序集合R，

為空集；

(b)將R[l]與R[i]交換，并將i算作已排序集合中的元素位置,

更新待排序集合中最后一個元素的位置M-1,此時待排序集合

R={R[1],R[2],R[i]},已排序集合R'={R[i+l],R[i+2],R[n]}0

顯然，待排序集合R={R[1],R[2],…,R[i]}中只有根結(jié)點R[l]不滿足

大根堆的條件，通過下移R[l]重新將R整理為大根堆；

(c)重復(fù)上一步驟直至待排序集合區(qū)={41]},此時直接將R[l]

作為已排序集合R'中的元素，堆排序過程結(jié)束。

10.請簡述冒泡排序的具體步驟。

冒泡排序是一種簡單排序算法，其具體步驟為：

(a)初始已排序區(qū)為空，待排序區(qū)包含所有待排序元素。

(b)在一輪排序中，對待排序區(qū)所有相鄰元素從前至后進(jìn)行兩

兩比較，若相鄰兩個元素次序相反(即前一個元素的關(guān)鍵字值大于后

一個元素的關(guān)鍵字值)，則交換它們的位置。每輪排序后，待排序區(qū)

中的最大元素會移到待排序區(qū)的尾部，將待排序區(qū)的最后一個元素放

到已排序區(qū)的頭部。

(c)重復(fù)上一步驟直至待排序區(qū)中只剩下一個元素或者在一輪

排序中沒有出現(xiàn)相鄰元素交換的情況，此時直接將待排序區(qū)中的所有

元素按原次序放到已排序區(qū)的頭部，冒泡排序結(jié)束。

11.請簡述快速排序中劃分的含義和過程。

劃分的含義：

劃分是以指定元素x為基準(zhǔn)將一個集合R分為兩個子集Ri和R2,

其中Ri中的元素都小于或等于x,R2中的元素都大于或等于X。

劃分的過程：

對于包含(high-low+l)個元素的待排序集合R={R[low],

R[low+1],R[high]},以R[k](low<k<high)為基準(zhǔn)對其進(jìn)行劃分

的具體過程為：

(a)令i、J分別指向集合R的第一個元素和最后一個元素(即

i=low、j=high),并將R[k]與R[i]交換(即初始基準(zhǔn)元素在i所指向

的位置，此時基準(zhǔn)元素前面沒有任何元素，下面對基準(zhǔn)元素后面、位

置在i+1至Ijj之間的元素按照從后至前的順序逐一檢查其是否大于或

等于基準(zhǔn)元素）。

（b）若_]!』且咫心對],則令j=j-l,重復(fù)直至或j==i。

上述處理后，若j!=i（即通過R[jkR[i]這個條件退出循環(huán)）則將R[j]

與R[i]交換'i=i+l,并轉(zhuǎn)到下一步（該步處理結(jié)束后，基準(zhǔn)元素在j

所指向的位置，此時基準(zhǔn)元素后面的元素都大于或等于基準(zhǔn)元素，而

位置i前面的元素都小于或等于基準(zhǔn)元素，下面對基準(zhǔn)元素前面、位

置在i至Uj-1之間的元素按照從前至后的順序逐一檢查其是否小于或

等于基準(zhǔn)元素）。

（c）若i!=j且R[i]<R[j],則令i=i+l,重復(fù)直至R[i]>R[j]或i==j。

上述處理后，若i!=j（即通過R[i]>R[j]這個條件退出循環(huán)）則將R[i]

與R[j]交換'并回到上一步（該步處理結(jié)束后，基準(zhǔn)元素在i

所指向的位置，此時基準(zhǔn)元素前面的元素都小于或等于基準(zhǔn)元素，而

位置j后面的元素都大于或等于基準(zhǔn)元素，下面繼續(xù)對基準(zhǔn)元素后面、

位置在i+1至叮之間的元素按照從后至前的順序逐一檢查其是否大于

或等于基準(zhǔn)元素）；否則集合劃分操作結(jié)束。

12.請簡述快速排序的具體步驟。

快速排序就是對集合不斷劃分的過程：通過劃分可以將一個集合

分為兩個子集合，若子集合中元素數(shù)目大于1則再對子集合分別進(jìn)行

劃分，重復(fù)該過程直至最終每個子集合中元素數(shù)目都小于或等于1時

快速排序結(jié)束。

13.請簡述二路歸并排序的具體步驟。

二路歸并排序的具體步驟為：

(a)對于包含n個元素的待排序集合，將其分為n個長度為1

的子序列。

(b)將每兩個相鄰的子序列進(jìn)行歸并，得到l_n/2」個長度為2

的子序列和0或1個長度為1的子序列。

(c)在此基礎(chǔ)上，再對每兩個相鄰的子序列進(jìn)行歸并，得到Ln/4」

個長度為4的子序列和0或1個長度小于4的子序列。

(d)重復(fù)該過程直至得到一個長度為n的有序序列為止。

14.請簡述箱排序的具體步驟。

箱排序的具體步驟為：

(1)假設(shè)待排序元素的取值范圍為則箱子數(shù)量為n,

設(shè)置包含n個元素的隊列集合B={