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

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

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

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

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

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

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

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

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

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

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