數(shù)據(jù)結(jié)構(gòu)章節(jié)練習題及答案7

1、第7章排序算法.請簡述排序的作用。排序的作用是將一個待排序元素集合按關(guān)鍵字遞增(或遞減)順 序整理為一個有序序列。.請簡述穩(wěn)定排序和不穩(wěn)定排序的含義。假設(shè)采用某種排序算法對任一組元素進行排序，在排序前后，那些 具有相同關(guān)鍵字值的元素之間的相對次序都保持不變，那么將這種排序 算法稱為是穩(wěn)定的，否那么稱為是不穩(wěn)定的。.請簡述各種排序算法的適用范圍。排序算法的適用范圍如下:(a)直接插入排序、簡單項選擇擇排序和冒泡排序都是簡單排序算法，它們的時間復(fù)雜度和空間復(fù)雜度分別為0(1?)和0(1)。假設(shè)待排序 元素數(shù)量n較小，可以選用直接插入排序和冒泡排序。另外，當待排 序元素基本有序時，也應(yīng)選用直接插入排

2、序和冒泡排序，此時時間復(fù) 雜度都能到達0(n)。假設(shè)元素本身數(shù)據(jù)量較大，元素移動操作代價較高, 那么應(yīng)選用平均移動元素次數(shù)最少的簡單項選擇擇排序。希爾排序是對直接 插入排序算法的改進，大大降低了時間復(fù)雜度，但它是一種不穩(wěn)定的 排序算法。(b)堆排序、快速排序和歸并排序主要適用于待排序元素數(shù)量 n較大的情況，當待排序元素數(shù)量n較小時，它們的性能有可能劣于簡單排序算法。因此，在實際應(yīng)用時，快速排序算法和歸并排序算法 經(jīng)常與簡單排序算法結(jié)合使用（例如，可以先用快速排序算法將集合 劃分為規(guī)模更小的子集合，對于元素數(shù)量較小的子集合，那么用直接插 入排序算法進行排序）。在所有平均時間復(fù)雜度為O（nlog2

3、n）的算法 中，盡管快速排序在最壞情況下時間復(fù)雜度較高，但它通常被認為是 平均性能最好的一種算法，并且通過優(yōu)化可以降低最壞情況出現(xiàn)的概 率。歸并排序是一種穩(wěn)定的排序算法，其時間性能一般要優(yōu)于堆排序, 但它所需要的輔助空間較多，當應(yīng)用環(huán)境要求排序前后具有相同值的 元素相對次序不能改變時可以考慮使用。堆排序所需的輔助空間最 少，當可用空間非常有限時可以考慮使用。（c）箱排序和基數(shù)排序的時間復(fù)雜度最低，但它們的空間復(fù)雜度最高。箱排序主要適用于待排序元素長度（即d值）較小的情況， 在實際中應(yīng)用不多；基數(shù)排序是箱排序的改進，主要適用于整數(shù)或字 符串的排序，或者與其他排序算法結(jié)合進行實數(shù)的排序（例如，可以

4、 先用基數(shù)排序算法按整數(shù)局部將元素分成假設(shè)干個子集合，再對每個子 集合應(yīng)用直接插入排序算法進行排序）。.請簡述插入排序、選擇排序、交換排序、歸并排序和分配排序的原理。插入排序：按關(guān)鍵字大小每次將一個待排序的元素插入到已排序 的序列中，直至所有元素都插入完畢。選擇排序：每次從待排序的元素中選擇具有最小（或最大）關(guān)鍵字的元素放到已排序序列的尾部（或頭部），直至所有元素都排序完 畢。交換排序：從待排序的元素中選擇兩個次序相反的元素進行交換，直至任意兩個元素的次序都正確。K路歸并排序：每次將K (KN2)個已排序的子序列組合在一起, 形成一個有序的序列，重復(fù)該過程直至得到一個包含所有待排序元素 的有序

5、序列。分配排序：根據(jù)元素本身所具有的值將各元素逐一映射到一組有 序空間中，最后再依次從有序空間中將各元素取出即形成了排序結(jié) 果O.請簡述直接插入排序的具體步驟。直接插入排序是一種簡單排序算法，其具體步驟為：(a)初始已排序區(qū)為空，將第一個待排序的元素插入到已排序 區(qū)中。(b)將后繼每一個待排序的元素依次取出，并按照關(guān)鍵字大小 將其插入到已排序區(qū)中的適當位置，使該序列仍然有序。(c)重復(fù)上一步驟直至將待排序的元素都插入到已排序序列中。.請簡述希爾排序的具體步驟。希爾排序，又稱為“縮小增量排序”，其具體步驟為：(a)令n為待排序元素數(shù)目，設(shè)置增量序列do,di, .,dk,其 中 ndodi.dk

6、=lo(b)按增量& (i依次取值為0, 1, k)將待排序元素分為& 組，將所有下標距離為由的倍數(shù)的元素放在同一組中，即R1,R1 + di,Rl+2*di,在第一組中,R2, R2+ di, R2+2*di,在第二組 中，依此類推。然后分別在各組內(nèi)進行直接插入排序。(C)重復(fù)上一步驟直至最后以1為增量對所有待排序元素進行 直接插入排序。.請簡述簡單項選擇擇排序的具體步驟。簡單項選擇擇排序是一種簡單排序算法，其具體步驟為：(a)初始已排序區(qū)為空，待排序區(qū)包含所有待排序元素。(b)從待排序區(qū)中選擇具有最小關(guān)鍵字的元素，將其與待排序 區(qū)的第一個元素交換位置，并將該位置加到已排序區(qū)中。(c)重復(fù)上

7、一步驟直至所有元素都排序完畢。.請簡述堆的定義和堆的構(gòu)建過程。堆的定義：對于包含n個元素的集合R=R1, R2,Rn,假設(shè)滿足：RiWR2*i且RiSR2*i+l(即R所表示的完全二叉樹中 每一棵子樹的根結(jié)點的值均不大于其孩子結(jié)點的值)。(2)或 RiR2*iK Ri NR2*i+l(即 R 所表示的完全二叉樹 中每一棵子樹的根結(jié)點的值均不小于其孩子結(jié)點的值)。那么稱集合R為堆。假設(shè)滿足前一個條件那么稱R為小根堆，滿足后 一個條件那么稱R為大根堆。堆的構(gòu)建過程：堆一般采用自底向上的構(gòu)建方法，即在將以某一結(jié)點為根結(jié)點的 二叉樹構(gòu)建成堆之前，先將其左子樹和右子樹構(gòu)建成堆。以葉子結(jié)點 為根的子樹必然

8、是堆，因此，對于由n個元素構(gòu)成的完全二叉樹，其 對應(yīng)的堆的構(gòu)建過程從RLn/2作為根結(jié)點的子樹開始，依次對 RLn/2j-lx R|_n/2-2、Rl作為根結(jié)點的樹進行堆的構(gòu)建。在將一棵Ri作為根結(jié)點的子樹整理為堆時，只有根結(jié)點不滿足 堆的條件，因此，需將根結(jié)點與后繼層中的結(jié)點依次比擬并不斷將根 結(jié)點下移直至該子樹滿足堆的條件，這里以大根堆構(gòu)建為例介紹其具 體過程：(a)假設(shè)Ri存在左孩子R2*i,那么令j=2*i；假設(shè)Ri存在右孩子 R2*i+1且 R2*i+lR2*i,那么令 j=2*i+l。將 Rj與 Ri比擬，假設(shè) Ri較小,那么將Ri和Rj交換,并令i=j。(b)重復(fù)上述步驟直至Ri

9、無孩子結(jié)點或Ri比其孩子結(jié)點都 大，此時該子樹即為堆。.請簡述堆排序的具體步驟。堆排序的具體過程：(a)采用自底向上的方法將包含n個元素的待排序集合R=R1, R2,.,Rn整理為大根堆，其元素數(shù)目i=n,初始時已排序集合R 為空集；(b)將Rl與Ri交換，并將i算作已排序集合中的元素位置, 更新待排序集合中最后一個元素的位置i二i-1,此時待排序集合 R=R1, R2,Ri,已排序集合 RRi+l, Ri+2, Rno 顯然,待排序集合R=R1, R，,Ri中只有根結(jié)點Rl不滿足 大根堆的條件，通過下移Rl重新將R整理為大根堆；(c)重復(fù)上一步驟直至待排序集合R=此時直接將Rl 作為已排序集

10、合R中的元素，堆排序過程結(jié)束。.請簡述冒泡排序的具體步驟。冒泡排序是一種簡單排序算法，其具體步驟為：(a)初始已排序區(qū)為空，待排序區(qū)包含所有待排序元素。(b)在一輪排序中，對待排序區(qū)所有相鄰元素從前至后進行兩 兩比擬，假設(shè)相鄰兩個元素次序相反(即前一個元素的關(guān)鍵字值大于后 一個元素的關(guān)鍵字值)，那么交換它們的位置。每輪排序后，待排序區(qū) 中的最大元素會移到待排序區(qū)的尾部，將待排序區(qū)的最后一個元素放 到已排序區(qū)的頭部。(c)重復(fù)上一步驟直至待排序區(qū)中只剩下一個元素或者在一輪 排序中沒有出現(xiàn)相鄰元素交換的情況，此時直接將待排序區(qū)中的所有 元素按原次序放到已排序區(qū)的頭部，冒泡排序結(jié)束。.請簡述快速排序

11、中劃分的含義和過程。劃分的含義：劃分是以指定元素x為基準將一個集合R分為兩個子集Ri和R2, 其中Ri中的元素都小于或等于x, R2中的元素都大于或等于xo劃分的過程：對于包含(high-low+1)個元素的待排序集合R=Rlow, Rlow+1, .,Rhigh,以 Rk (lowkhigh)為基準對其進行劃分 的具體過程為：(a)令i、j分別指向集合R的第一個元素和最后一個元素(即 i=lowx j=high),并將Rk與Ri交換(即初始基準元素在i所指向 的位置，此時基準元素前面沒有任何元素，下面對基準元素后面、位 置在i+1至I之間的元素按照從后至前的順序逐一檢查其是否大于或 等于基準

12、元素）。（b）假設(shè) j!=i 且 RjNRi,那么令重復(fù)直至 RjRi或 j=i。上述處理后，假設(shè)j!=i （即通過RUkRE這個條件退出循環(huán)）那么將Rj 與Ri交換、i=i+L并轉(zhuǎn)到下一步（該步處理結(jié)束后，基準元素在J 所指向的位置，此時基準元素后面的元素都大于或等于基準元素，而 位置i前面的元素都小于或等于基準元素，下面對基準元素前面、位 置在i至j-1之間的元素按照從前至后的順序逐一檢查其是否小于或 等于基準元素）。（c）假設(shè) i!=j 且 RiR|j,那么令 i=i+l,重復(fù)直至或 i=j0上述處理后，假設(shè)i!刁（即通過這個條件退出循環(huán)）那么將RU 與Rj交換、j=j-1,并回到上一步

13、（該步處理結(jié)束后，基準元素在i 所指向的位置，此時基準元素前面的元素都小于或等于基準元素，而 位置j后面的元素都大于或等于基準元素，下面繼續(xù)對基準元素后面、 位置在i+1至I之間的元素按照從后至前的順序逐一檢查其是否大于 或等于基準元素）；否那么集合劃分操作結(jié)束。.請簡述快速排序的具體步驟?？焖倥判蚓褪菍喜粩鄤澐值倪^程：通過劃分可以將一個集合 分為兩個子集合，假設(shè)子集合中元素數(shù)目大于1那么再對子集合分別進行 劃分，重復(fù)該過程直至最終每個子集合中元素數(shù)目都小于或等于1時 快速排序結(jié)束。.請簡述二路歸并排序的具體步驟。二路歸并排序的具體步驟為：(a)對于包含n個元素的待排序集合，將其分為n個長

14、度為1 的子序列。(b)將每兩個相鄰的子序列進行歸并，得到Ln/2個長度為2 的子序列和0或1個長度為1的子序列。(c)在此基礎(chǔ)上，再對每兩個相鄰的子序列進行歸并，得到n/4 個長度為4的子序列和0或1個長度小于4的子序列。(d)重復(fù)該過程直至得到一個長度為n的有序序列為止。.請簡述箱排序的具體步驟。箱排序的具體步驟為：(1)假設(shè)待排序元素的取值范圍為mm+n-1,那么箱子數(shù)量為n, 設(shè)置包含n個元素的隊列集合B=BO, Bl,代表n個箱子。(2)依次取出每一個待排序元素，假設(shè)其值為m+i(i=O, 那么通過入隊操作將其放在箱子Bi中。(3)從B0開始，依次檢查集合B中每一個隊列所代表的箱子, 假設(shè)箱子不為空，那么通過出隊操作將箱子中的元素逐個取出并依次加到 已排序集合中。.請簡述基數(shù)排序的具體步驟?；鶖?shù)排序是對箱排序的改進和推廣，它先將待排序元素按規(guī)那么分解得到多個分量、再根據(jù)每一個分量對元素進行屢次箱排序。(a)對