數(shù)據(jù)結(jié)構(gòu)與算法7

第7章排序算法（4課時(shí)）排序，又稱分類，是計(jì)算機(jī)進(jìn)行數(shù)據(jù)處理時(shí)經(jīng)常使用的一種重要操作。本章在介紹排序算法基本概念及對(duì)各種常見排序算法進(jìn)行性能比較的基礎(chǔ)上，重點(diǎn)講解插入排序、選擇排序、交換排序、歸并排序和分配排序等常用排序算法的原理和實(shí)現(xiàn)方法。排序，是指將一個(gè)待排序元素集合按關(guān)鍵字遞增（或遞減）順序整理為一個(gè)有序序列的過程。例如，對(duì)于一組具有關(guān)鍵字值{43,56,37,28,17,39,22,70}的數(shù)據(jù)元素集合{R1,R2,…,R8}，按關(guān)鍵字遞增順序的排序結(jié)果為{R5,R7,R4,R3,R6,R1,R2,R8}（對(duì)應(yīng)的關(guān)鍵字值為{17,22,28,37,39,43,56,70}）。本教材以遞增排序?yàn)槔v解排序算法。若任意兩個(gè)待排序元素都具有不同的關(guān)鍵字值，則排序結(jié)果必然唯一；若多個(gè)待排序元素具有相同的關(guān)鍵字值，則排序結(jié)果可能不唯一。若采用某種排序算法對(duì)任一組元素進(jìn)行排序，在排序前后，那些具有相同關(guān)鍵字值的元素之間的相對(duì)次序都保持不變，則將這種排序算法稱為是穩(wěn)定的，否則稱為是不穩(wěn)定的。例如，對(duì)于一組具有關(guān)鍵字值{43,56,37,28,17,37,22,70}的數(shù)據(jù)元素集合{R1,R2,…,R8}，若根據(jù)算法A得到的排序結(jié)果為{R5,R7,R4,R6,R3,R1,R2,R8}（對(duì)應(yīng)的關(guān)鍵字值為{17,22,28,37,37,43,56,70}），則算法A是不穩(wěn)定的。這里需要注意，不穩(wěn)定的排序算法并不一定對(duì)每一組元素都會(huì)得到不穩(wěn)定的排序結(jié)果，只要一種排序算法在某一組元素上得到不穩(wěn)定的排序結(jié)果，則這種排序算法就是不穩(wěn)定的。7.1排序算法及常見排序算法比較排序算法有很多，各有優(yōu)缺點(diǎn)，一般從時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性三個(gè)角度衡量算法優(yōu)劣并結(jié)合實(shí)際應(yīng)用條件選取適合的排序算法。其中，時(shí)間復(fù)雜度主要看排序時(shí)元素之間的比較次數(shù)和元素的移動(dòng)次數(shù)；空間復(fù)雜度主要看排序時(shí)除了待排序元素所占據(jù)的空間外還需要多大的輔助空間。排序分為兩類：內(nèi)排序和外排序。內(nèi)排序是指待排序列完全存放在內(nèi)存中所進(jìn)行的排序過程，適合不太大的元素序列。外排序是指排序過程中還需訪問外存儲(chǔ)器，足夠大的元素序列，因不能完全放入內(nèi)存，只能使用外排序。7.1排序算法及常見排序算法比較1.排序算法的適用范圍直接插入排序、簡單選擇排序和冒泡排序都是簡單排序算法，它們的時(shí)間復(fù)雜度和空間復(fù)雜度分別為O(n2)和O(1)。若待排序元素?cái)?shù)量n較小，可以選用直接插入排序和冒泡排序。另外，當(dāng)待排序元素基本有序時(shí)，也應(yīng)選用直接插入排序和冒泡排序，此時(shí)時(shí)間復(fù)雜度都能達(dá)到O(n)。若元素本身數(shù)據(jù)量較大，元素移動(dòng)操作代價(jià)較高，則應(yīng)選用平均移動(dòng)元素次數(shù)最少的簡單選擇排序。希爾排序是對(duì)直接插入排序算法的改進(jìn)，大大降低了時(shí)間復(fù)雜度，但它是一種不穩(wěn)定的排序算法。7.1排序算法及常見排序算法比較堆排序、快速排序和歸并排序主要適用于待排序元素?cái)?shù)量n較大的情況，當(dāng)待排序元素?cái)?shù)量n較小時(shí)，它們的性能有可能劣于簡單排序算法。在所有平均時(shí)間復(fù)雜度為O(nlog2n)的算法中，盡管快速排序在最壞情況下時(shí)間復(fù)雜度較高，但它通常被認(rèn)為是平均性能最好的一種算法。歸并排序是一種穩(wěn)定的排序算法，其時(shí)間性能一般要優(yōu)于堆排序，但它所需要的輔助空間較多，堆排序所需的輔助空間最少，當(dāng)可用空間非常有限時(shí)可以考慮使用。箱排序和基數(shù)排序的時(shí)間復(fù)雜度最低，但它們的空間復(fù)雜度最高。箱排序主要適用于待排序元素長度（即d值）較小的情況，在實(shí)際中應(yīng)用不多；基數(shù)排序是箱排序的改進(jìn)，主要適用于整數(shù)或字符串的排序，或者與其他排序算法結(jié)合進(jìn)行實(shí)數(shù)的排序。7.1排序算法及常見排序算法比較2.排序算法的復(fù)雜度下面對(duì)各類排序算法的性能作一下比較。設(shè)待排序元素?cái)?shù)目為n、待排序元素的長度為d、待排序元素每一位可能取值的個(gè)數(shù)為rd（例如，待排序元素為至多4位的整數(shù)，此時(shí)d=4、rd=10；再如，待排序元素為長度至多為20的字符串、每一字符取值為'a'~'z'，此時(shí)d=20、rd=26），則各排序算法的性能如表7-1所示。7.1排序算法及常見排序算法比較插入排序是指按關(guān)鍵字大小每次將一個(gè)待排序的元素插入到已排序的序列中，直至所有元素都插入完畢。插入排序有多種形式，下面主要介紹直接插入排序和希爾排序兩種算法。7.2插入排序7.2插入排序7.2.1直接插入排序7.2.2希爾排序直接插入排序是一種簡單排序算法，其具體步驟為：

初始已排序區(qū)為空，將第一個(gè)待排序的元素插入到已排序區(qū)中。將后繼每一個(gè)待排序的元素依次取出，并按照關(guān)鍵字大小將其插入到已排序區(qū)中的適當(dāng)位置，使該序列仍然有序。重復(fù)上一步驟直至將待排序的元素都插入到已排序序列中。7.2插入排序7.2.1直接插入排序直接插入排序的算法描述如下：【描述7-1】直接插入排序的算法描述。

分析：從圖7-1中可見，已排序元素?cái)?shù)目與待排序元素?cái)?shù)目之和保持不變，因此，可以使用同一個(gè)數(shù)組的不同部分分別保存已排序序列和未排序元素集合。如定義一個(gè)一維數(shù)組R，在第i趟排序后R中下標(biāo)為1到i+1的位置用于存放已排序序列、之后的位置用于存放未排序元素集合。7.2插入排序7.2.1直接插入排序7.2插入排序7.2.1直接插入排序

希爾排序，又稱為“縮小增量排序”，其具體步驟為：令n為待排序元素?cái)?shù)目，設(shè)置增量序列{d0,d1,…,dk}，其中n>d0>d1>…>dk=1。按增量di（i依次取值為0,1,…,k）將待排序元素分為di組，將所有下標(biāo)距離為di的倍數(shù)的元素放在同一組中，即R[1],R[1+di],R[1+2*di],…在第一組中，R[2],R[2+di],R[2+2*di],…在第二組中，…，依此類推。然后分別在各組內(nèi)進(jìn)行直接插入排序。重復(fù)上一步驟直至最后以1為增量對(duì)所有待排序元素進(jìn)行直接插入排序。7.2插入排序7.2.2希爾排序7.2插入排序7.2.2希爾排序提示：希爾排序的比較次數(shù)和移動(dòng)次數(shù)依賴于增量序列，為了具有較好的性能，一般增量序列中的元素應(yīng)避免互為倍數(shù)的情況。另外，增量序列中的最后一個(gè)元素必須是1。希爾排序算法的時(shí)間復(fù)雜度與使用的增量序列有關(guān)，但如何針對(duì)特定增量序列計(jì)算算法的時(shí)間復(fù)雜度以及如何選擇增量序列使算法的時(shí)間復(fù)雜度最低仍是數(shù)學(xué)上尚未解決的難題。因此，這里僅給出定性的結(jié)論：當(dāng)待排序元素?cái)?shù)目n很大時(shí)，希爾排序算法的時(shí)間復(fù)雜度要遠(yuǎn)低于直接插入排序算法。與直接插入排序算法相同，希爾排序算法只需要一個(gè)監(jiān)視哨的輔助空間，因此空間復(fù)雜度也為O(1)。從圖7-2可以看出，希爾排序是不穩(wěn)定的。7.2插入排序7.2.2希爾排序7.3選擇排序選擇排序是指每次從待排序的元素中選擇具有最?。ɑ蜃畲螅╆P(guān)鍵字的元素放到已排序序列的尾部（或頭部），直至所有元素都排序完畢。選擇排序有多種形式，下面主要介紹簡單選擇排序和堆排序兩種。7.3選擇排序7.3.1簡單選擇排序7.3.2堆排序7.3選擇排序簡單選擇排序是一種簡單排序算法，其具體步驟為：1）初始已排序區(qū)為空，待排序區(qū)包含所有待排序元素。2）從待排序區(qū)中選擇具有最小關(guān)鍵字的元素，將其與待排序區(qū)的第一個(gè)元素交換位置，并將該位置加到已排序區(qū)中。3）重復(fù)上一步驟直至所有元素都排序完畢。7.3.1簡單選擇排序7.3選擇排序7.3.1簡單選擇排序7.3選擇排序在簡單選擇排序算法的每輪排序中，都需要對(duì)待排序區(qū)的所有元素進(jìn)行比較，最后只有具有最小關(guān)鍵字的元素被取出，而其余待排序區(qū)中的元素在下一輪排序時(shí)需重新比較，這樣就使得許多比較操作重復(fù)多次，增加了算法的時(shí)間復(fù)雜度。例如，對(duì)于圖7-3所示的簡單選擇排序過程，在第1輪選擇排序中，37和28已作過比較；而在第2輪和第3輪選擇排序中，37和28會(huì)再作比較。堆排序是對(duì)簡單選擇排序算法的優(yōu)化，它利用完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)減少元素之間的重復(fù)比較。堆排序的過程實(shí)質(zhì)上就是不斷創(chuàng)建堆的過程，下面先給出堆的概念，然后再給出堆排序算法。7.3.2堆排序1.堆

對(duì)于包含n個(gè)元素的集合R={R[1],R[2],…,R[n]}，若滿足：R[i]≤R[2*i]且R[i]≤R[2*i+1]（即R所表示的完全二叉樹中每一棵子樹的根結(jié)點(diǎn)的值均不大于其孩子結(jié)點(diǎn)的值）；或R[i]≥R[2*i]且R[i]≥R[2*i+1]（即R所表示的完全二叉樹中每一棵子樹的根結(jié)點(diǎn)的值均不小于其孩子結(jié)點(diǎn)的值）。

則稱集合R為堆。若滿足前一個(gè)條件則稱R為小根堆，滿足后一個(gè)條件則稱R為大根堆。7.3選擇排序7.3.2堆排序例如，{56,43,37,30,17,37,22,28}是一個(gè)大根堆，{17,28,22,30,56,37,37,43}是一個(gè)小根堆，它們所對(duì)應(yīng)的完全二叉樹表示分別如圖7-4（a）和7-4（b）所示。7.3選擇排序7.3.2堆排序2.建堆方法

建堆是指假設(shè)已存在一棵由元素關(guān)鍵字作為結(jié)點(diǎn)的完全二叉樹，現(xiàn)在調(diào)整該二叉樹中結(jié)點(diǎn)的值，使調(diào)整后的二叉樹表示的元素集合是一個(gè)堆。

堆一般采用自底向上的構(gòu)建方法，即在將以某一結(jié)點(diǎn)為根結(jié)點(diǎn)的二叉樹構(gòu)建成堆之前，先將其左子樹和右子樹構(gòu)建成堆。以葉子結(jié)點(diǎn)為根的子樹必然是堆，因此，對(duì)于由n個(gè)元素構(gòu)成的完全二叉樹，其對(duì)應(yīng)的堆的構(gòu)建過程從R[n/2]作為根結(jié)點(diǎn)的子樹開始，依次對(duì)R[n/2-1]、R[n/2-2]、…、R[1]作為根結(jié)點(diǎn)的樹進(jìn)行堆的構(gòu)建。例如，對(duì)于集合{30,22,37,17,28,37,56,43}，其對(duì)應(yīng)的大根堆的構(gòu)建過程如圖7-5所示，在每一步處理時(shí)將虛線框中的子樹整理為堆。7.3選擇排序7.3.2堆排序7.3選擇排序7.3.2堆排序在將一棵R[i]作為根結(jié)點(diǎn)的子樹整理為堆時(shí)，只有根結(jié)點(diǎn)不滿足堆的條件，因此，需將根結(jié)點(diǎn)與后繼層中的結(jié)點(diǎn)依次比較并不斷將根結(jié)點(diǎn)下移直至該子樹滿足堆的條件，這里以大根堆構(gòu)建為例介紹其具體過程：若R[i]存在左孩子R[2*i]，則令j=2*i；若R[i]存在右孩子R[2*i+1]且R[2*i+1]>R[2*i]，則令j=2*i+1。將R[j]與R[i]比較，若R[i]較小，則將R[i]和R[j]交換，并令i=j。重復(fù)上述步驟直至R[i]無孩子結(jié)點(diǎn)或R[i]比其孩子結(jié)點(diǎn)都大，此時(shí)該子樹即為堆。例如，對(duì)于圖7-5所示的大根堆構(gòu)建過程，圖7-5（c）到圖7-5（d）的作用是將整棵樹整理為堆，其具體步驟為：將根結(jié)點(diǎn)R[1]與具有較大值的右孩子結(jié)點(diǎn)R[3]比較，有R[1]<R[3]，因此將R[1]和R[3]交換；將R[3]與左孩子結(jié)點(diǎn)R[6]比較（左右孩子同樣大時(shí)以左孩子結(jié)點(diǎn)優(yōu)先），有R[3]<R[6]，因此將R[3]和R[6]交換；R[6]無孩子結(jié)點(diǎn)，此時(shí)該樹已整理為堆。7.3選擇排序7.3.2堆排序3.堆排序算法下面給出堆排序的具體過程：采用自底向上的方法將包含n個(gè)元素的待排序集合R={R[1],R[2],…,R[n]}整理為大根堆，其元素?cái)?shù)目i=n，初始時(shí)已排序集合R'為空集；將R[1]與R[i]交換，并將i算作已排序集合中的元素位置，更新待排序集合中最后一個(gè)元素的位置i=i-1，此時(shí)待排序集合R={R[1],R[2],…,R[i]}，已排序集合R'={R[i+1],R[i+2],…,R[n]}。顯然，待排序集合R={R[1],R[2],…,R[i]}中只有根結(jié)點(diǎn)R[1]不滿足大根堆的條件，通過下移R[1]重新將R整理為大根堆；重復(fù)上一步驟直至待排序集合R={R[1]}，此時(shí)直接將R[1]作為已排序集合R'中的元素，堆排序過程結(jié)束。7.3選擇排序7.3.2堆排序例如，對(duì)于集合{30,22,37,17,28,37,56,43}，其堆排序過程如圖7-6所示?？梢姡@里給出的堆排序選擇元素的順序與前面給出的簡單選擇排序正好相反，每輪堆排序從待排序集合中選擇最大元素并將其放到已排序集合的頭部。本書中給出的是常見實(shí)現(xiàn)方式，實(shí)際上可以利用小根堆實(shí)現(xiàn)堆排序使其選擇元素的順序與前面給出的簡單選擇排序相同，也可以更改前面給出的簡單選擇排序使其選擇元素的順序與這里給出的利用大根堆實(shí)現(xiàn)的堆排序相同。7.3選擇排序7.3.2堆排序7.3選擇排序7.3.2堆排序7.3選擇排序7.3.2堆排序

堆排序算法的時(shí)間復(fù)雜度分析較為復(fù)雜，這里僅給出結(jié)論：堆排序算法在平均情況和最壞情況下所需的元素比較次數(shù)和元素移動(dòng)次數(shù)的時(shí)間復(fù)雜度均為O(nlog2n)。堆排序算法只在整理堆和進(jìn)行元素交換時(shí)需要一個(gè)輔助空間，因此空間復(fù)雜度為O(1)。從圖7-6可以看出，堆排序是不穩(wěn)定的。

提示：要實(shí)現(xiàn)降序排序，只要在建立初始堆和整理堆時(shí)按照小根堆處理就行了。感興趣的讀者可以自己對(duì)程序進(jìn)行修改。7.3選擇排序7.3.2堆排序7.4交換排序交換排序是指從待排序的元素中選擇兩個(gè)次序相反的元素進(jìn)行交換，直至任意兩個(gè)元素的次序都正確。下面介紹冒泡排序和快速排序兩種交換排序方法。7.4交換排序7.4.1冒泡排序7.4.2快速排序7.4.1冒泡排序7.4交換排序冒泡排序是一種簡單排序算法，其具體步驟為：初始已排序區(qū)為空，待排序區(qū)包含所有待排序元素。在一輪排序中，對(duì)待排序區(qū)所有相鄰元素從前至后進(jìn)行兩兩比較，若相鄰兩個(gè)元素次序相反（即前一個(gè)元素的關(guān)鍵字值大于后一個(gè)元素的關(guān)鍵字值），則交換它們的位置。每輪排序后，待排序區(qū)中的最大元素會(huì)移到待排序區(qū)的尾部，將待排序區(qū)的最后一個(gè)元素放到已排序區(qū)的頭部。重復(fù)上一步驟直至待排序區(qū)中只剩下一個(gè)元素或者在一輪排序中沒有出現(xiàn)相鄰元素交換的情況，此時(shí)直接將待排序區(qū)中的所有元素按原次序放到已排序區(qū)的頭部，冒泡排序結(jié)束。7.4.1冒泡排序7.4交換排序7.4.1冒泡排序7.4交換排序7.4交換排序在冒泡排序算法中，僅對(duì)相鄰元素進(jìn)行比較和交換。通過每次交換，元素前移或后移一個(gè)位置。若排序前元素位置為i，排序后元素位置為j，則在排序過程中為了將該元素移到正確位置需要做|j-i|次交換操作。因此，冒泡排序所需要的元素比較和移動(dòng)次數(shù)較多?？焖倥判蚴菍?duì)冒泡排序算法的優(yōu)化，它通過對(duì)待排序集合進(jìn)行逐層劃分，可以實(shí)現(xiàn)兩個(gè)相距較遠(yuǎn)元素的比較和交換操作，從而大大減少了元素的比較和移動(dòng)次數(shù)?？焖倥判虻倪^程實(shí)質(zhì)上就是不斷對(duì)待排序集合進(jìn)行劃分的過程，因此，在介紹快速排序之前，先說明劃分的作用和待排序集合劃分的過程。劃分是以指定元素x為基準(zhǔn)將一個(gè)集合R分為兩個(gè)子集R1和R2，其中R1中的元素都小于或等于x，R2中的元素都大于或等于x。例如，對(duì)于集合R={43,56,37,28,17,37,22,30}，以43為基準(zhǔn)，可以將其劃分為兩個(gè)子集R1={30,22,37,28,17,37}和R2={56}。7.4.2快速排序7.4交換排序?qū)τ诎?high-low+1)個(gè)元素的待排序集合R={R[low],R[low+1],…,R[high]}，以R[k]（low≤k≤high）為基準(zhǔn)對(duì)其進(jìn)行劃分的具體過程為：令i、j分別指向集合R的第一個(gè)元素和最后一個(gè)元素（即i=low、j=high），并將R[k]與R[i]交換（即初始基準(zhǔn)元素在i所指向的位置，此時(shí)基準(zhǔn)元素前面沒有任何元素，下面對(duì)基準(zhǔn)元素后面、位置在i+1到j(luò)之間的元素按照從后至前的順序逐一檢查其是否大于或等于基準(zhǔn)元素）。7.4.2快速排序7.4交換排序若j!=i且R[j]≥R[i]，則令j=j-1，重復(fù)直至R[j]<R[i]或j==i。若j!=i則將R[j]與R[i]交換、i=i+1，并轉(zhuǎn)到下一步（該步處理結(jié)束后，基準(zhǔn)元素在j所指向的位置，此時(shí)基準(zhǔn)元素后面的元素都大于或等于基準(zhǔn)元素，而位置i前面的元素都小于或等于基準(zhǔn)元素，下面對(duì)基準(zhǔn)元素前面、位置在i到j(luò)-1之間的元素按照從前至后的順序逐一檢查其是否小于或等于基準(zhǔn)元素）。若i!=j且R[i]≤R[j]，則令i=i+1，重復(fù)直至R[i]>R[j]或i==j。若i!=j則將R[i]與R[j]交換、j=j-1，并回到上一步（該步處理結(jié)束后，基準(zhǔn)元素在i所指向的位置，此時(shí)基準(zhǔn)元素前面的元素都小于或等于基準(zhǔn)元素，而位置j后面的元素都大于或等于基準(zhǔn)元素，下面繼續(xù)對(duì)基準(zhǔn)元素后面、位置在i+1到j(luò)之間的元素按照從后至前的順序逐一檢查其是否大于或等于基準(zhǔn)元素）；否則集合劃分操作結(jié)束。7.4.2快速排序7.4交換排序集合劃分操作結(jié)束后，i和j所共同指向的位置即是基準(zhǔn)元素所在的位置，子集合R1={R[low],…,R[i-1]}中的元素都小于或等于基準(zhǔn)元素R[i]，子集合R2={R[i+1],…,R[high]}中的元素都大于或等于基準(zhǔn)元素R[i]。例如，對(duì)于集合R={43,56,37,28,17,37,22,30}，以28為基準(zhǔn)，其劃分過程如圖7-8所示。7.4.2快速排序7.4交換排序7.4.2快速排序7.4交換排序集合劃分的算法描述如下：【描述7-6】集合劃分的算法描述。分析：在算法實(shí)現(xiàn)時(shí)，為了減少基準(zhǔn)元素的移動(dòng)次數(shù)，可以用R[0]保存基準(zhǔn)元素，每次將元素R[X]與基準(zhǔn)元素比較時(shí)直接將R[X]與R[0]比較即可，而每次將元素R[X]與基準(zhǔn)元素交換時(shí)只需將元素R[X]移入基準(zhǔn)元素應(yīng)在的位置即可。在最后找到基準(zhǔn)元素的正確位置后，將R[0]移入該位置。7.4.2快速排序7.4交換排序7.4.2快速排序圖7-8所對(duì)應(yīng)的算法實(shí)現(xiàn)處理過程如圖7-9所示。7.4交換排序快速排序就是對(duì)集合不斷劃分的過程：通過劃分可以將一個(gè)集合分為兩個(gè)子集合，若子集合中元素?cái)?shù)目大于1則再對(duì)子集合分別進(jìn)行劃分，重復(fù)該過程直至最終每個(gè)子集合中元素?cái)?shù)目都小于或等于1時(shí)快速排序結(jié)束。例如，對(duì)于集合R={37,43,26,30,17,37,22,28}，其快速排序過程如圖7-10所示（這里假設(shè)每次將待劃分集合中的第一個(gè)元素作為基準(zhǔn)元素）。7.4.2快速排序7.4交換排序7.4.2快速排序7.4交換排序【描述7-8】快速排序非遞歸實(shí)現(xiàn)的算法描述。分析：非遞歸快速排序需要利用棧實(shí)現(xiàn)，棧頂元素是當(dāng)前要?jiǎng)澐值募希ㄓ蒖ange類對(duì)象表示集合，其中兩個(gè)成員變量m_low和m_high分別保存待劃分集合的起始位置和結(jié)束位置）。具體步驟為：（1）將初始待排序集合進(jìn)棧；（2）取棧頂元素，若上一次出棧的是劃分后的兩個(gè)子集合中的后一個(gè)子集合，則表明其劃分后得到的兩個(gè)子集合也已劃分完畢，將棧頂元素出棧；若上一次出棧的是劃分后的兩個(gè)子集合中的前一個(gè)子集合，則表明其劃分后得到的兩個(gè)子集合中還有一個(gè)子集合沒有進(jìn)行劃分，將后一個(gè)子集合進(jìn)棧；否則，表明對(duì)棧頂元素所表示的集合還沒有進(jìn)行劃分，此時(shí)若棧頂集合長度大于1則對(duì)棧頂集合進(jìn)行劃分、并將劃分后得到的前一個(gè)子集合進(jìn)棧，若棧頂集合長度小于或等于1則不需進(jìn)行劃分、直接出棧即可；（3）重復(fù)步驟（2）直至棧為空。7.4.2快速排序K路歸并排序是指每次將K（K≥2）個(gè)已排序的子序列組合在一起，形成一個(gè)有序的序列，重復(fù)該過程直至得到一個(gè)包含所有待排序元素的有序序列。這里以二路歸并排序（下文簡稱歸并排序）為例介紹歸并排序的算法。歸并排序的具體步驟為：對(duì)于包含n個(gè)元素的待排序集合，將其分為n個(gè)長度為1的子序列；將每兩個(gè)相鄰的子序列進(jìn)行歸并，得到n/2個(gè)長度為2的子序列和0或1個(gè)長度為1的子序列；在此基礎(chǔ)上，再對(duì)每兩個(gè)相鄰的子序列進(jìn)行歸并，得到n/4個(gè)長度為4的子序列和0或1個(gè)長度小于4的子序列；重復(fù)該過程直至得到一個(gè)長度為n的有序序列為止。7.5歸并排序7.5歸并排序7.6分配排序前面介紹的排序算法都是通過對(duì)待排序集合中元素的比較和移動(dòng)來實(shí)現(xiàn)排序的。分配排序則采用了一種截然不同的思想，它不需要對(duì)元素進(jìn)行直接比較，而是根據(jù)元素本身所具有的值將各元素逐一映射到一組有序空間中，最后再依次從有序空間中將各元素取出即形成了排序結(jié)果。與前面學(xué)習(xí)的排序算法相比，分配排序一般有著更低的時(shí)間復(fù)雜度但更高的空間復(fù)雜度。下面介紹箱排序和基數(shù)排序兩種分配排序方法。7.6.1箱排序7.6.2基數(shù)排序7.6分配排序箱排序，又稱為桶排序，是指通過設(shè)置一些有序的箱子，將待排序集合中各元素根據(jù)它們的值逐一分配到各箱子中，最后再按箱子的順序依次將各元素從箱子中取出從而形成排序結(jié)果的一種排序算法。在箱排序中，箱子的個(gè)數(shù)由元素的取值范圍決定。例如，要將學(xué)生按其課程成績（設(shè)取值范圍為0~100之間的整數(shù)）排序，則需要設(shè)置101個(gè)箱子；要將學(xué)生按其學(xué)號(hào)（設(shè)學(xué)號(hào)為7位，取值范圍為0000000~9999999）排序，則需要設(shè)置10000000個(gè)箱子?？梢?，箱排序適用于取值范圍較小的情況。另外，在箱排序中，具有相同值的元素會(huì)放在同一個(gè)箱子里。例如，n名學(xué)生的課程成績都是m，那么在按課程成績排序時(shí)這n名學(xué)生對(duì)應(yīng)的是同一個(gè)箱子。此時(shí)，可以考慮每個(gè)箱子用一個(gè)線性表來保存若干個(gè)具有相同值的元素，在具體實(shí)現(xiàn)時(shí)通常使用隊(duì)列以保證排序過程是穩(wěn)定的。7.6分配排序7.6.1箱排序箱排序的具體步驟為：假設(shè)待排序元素的取值范圍為m~m+n-1，則箱子數(shù)量為n，設(shè)置包含n個(gè)元素的隊(duì)列集合B={B[0],B[1],…,B[n-1]}代表n個(gè)箱子。依次取出每一個(gè)待排序元素，若其值為m+i（i=0,1,…,n-1），則通過入隊(duì)操作將其放在箱子B[i]中。從B[0]開始，依次檢查集合B中每一個(gè)隊(duì)列所代表的箱子，若箱子不為空，則通過出隊(duì)操作將箱子中的元素逐個(gè)取出并依次加到已排序集合中。7.6分配排序7.6.1箱排序7.6分配排序7.6.1箱排序?qū)τ诎琻個(gè)元素的待排序集合，箱排序算法僅需進(jìn)行n次裝箱操作和n次出箱操作，因此箱排序在任何情況下的時(shí)間復(fù)雜度均為O(n)。箱排序的空間復(fù)雜度與待排序元素的長度有關(guān)系，若對(duì)d位數(shù)據(jù)組成的集合進(jìn)行箱排序，且數(shù)據(jù)的每一位可能取的值的個(gè)數(shù)為rd，那么需要rdd個(gè)箱子（例如，要對(duì)由4位十進(jìn)制整數(shù)組成的集合進(jìn)行箱排序，需設(shè)置104=10000個(gè)箱子），另外還需要設(shè)置與待排序元素?cái)?shù)量相同的輔助空間來存儲(chǔ)裝箱的元素，因此箱排序的空間復(fù)雜度為O(n+rdd)。箱排序用隊(duì)列存儲(chǔ)具有相同值的元素，位置靠前的同值元素裝箱時(shí)先入隊(duì)、出箱時(shí)先出隊(duì)，保證了同值元素的相對(duì)次序不會(huì)改變，因此歸并排序是