《數(shù)據(jù)結(jié)構(gòu)》考研課程PPT第七章排序的基本知識

排序的基本知識單獨的一個數(shù)據(jù)排序ABCDEFG12學(xué)號姓名數(shù)學(xué)政治總分3張進(jìn)456魏坤78高媛媛9朱雪帥如果待排序表中有兩個元素R、R,其對應(yīng)的關(guān)鍵字key;=key,且在排序前R在R前面，如果使用某一排序算法排序后，R仍然在R的前面，則稱這個排序算法是穩(wěn)定的，否則稱排序算法是不穩(wěn)定的。排序之后穩(wěn)定的不穩(wěn)定的穩(wěn)定的不穩(wěn)定的排序之后穩(wěn)定性和排序的性能是沒有關(guān)系的!直接插入排序：首先以一個元素為有序的序列，然后將后面的元素依次插入到有序的序列中合適的位置直到所有元素都插入有序序列。從第2個元素開始，因為第1個元素可以認(rèn)為是有序的如果待插入元素比有序序列的最后一個元素還大，那就不用插入了，直接放在原來的位置A[j+1]=A[j];//所有比待插入元素值大的都往后移一位，騰出空位=A[0];3有序序列中只要比這個待插入元素大，循環(huán)就有序序列中只要比這個待插入元素大，循環(huán)就所以第一個比較的元素就是有序序列的最后一個空間復(fù)雜度：在下標(biāo)為0處存儲哨兵，是常數(shù)個輔助空間大小，所以空間復(fù)雜度為O(1)時間復(fù)雜度：最壞情況下：整個序列都是逆序A[0]=A[];即外層for循環(huán)每一輪，內(nèi)層forfor(j=i-1;EQ\*jc3\*hps31\o\al(\s\up3(A[0),A[)EQ\*jc3\*hps31\o\al(\s\up3(]),j)EQ\*jc3\*hps31\o\al(\s\up3(e),])EQ\*jc3\*hps31\o\al(\s\up3(<),A)EQ\*jc3\*hps31\o\al(\s\up3(A),[j)EQ\*jc3\*hps31\o\al(\s\up3([j),]).key;--j)循環(huán)將執(zhí)行完整。A[0]=A[];即外層for循環(huán)每一輪，內(nèi)層for所以最壞情況下時間復(fù)雜度4要插到5前面，3要插到4前面，2要插入到3前面…移動1次移動2次移動3次時間復(fù)雜度：最好情況下：整個序列都是順序for(j=i-1;A[0].key<A[j].}即外層for循環(huán)每一輪，都只進(jìn)所以時間復(fù)雜度為O(n直接插入排序分析穩(wěn)定性5246413當(dāng)給關(guān)鍵字4排序時，前面的序列已經(jīng)是2456,根據(jù)算法比較4和有序序列的關(guān)鍵字大小。當(dāng)比較4和4的時候，已經(jīng)不滿足A[0].key<A[j].key。所以直接將4放在4后面。所以直接插入排序是穩(wěn)定性是穩(wěn)定的。分析排序算法穩(wěn)定性首先要熟悉算法的流程來判斷，當(dāng)結(jié)果不明顯時分析排序算法穩(wěn)定性首先要熟悉算法的流程來判斷，當(dāng)結(jié)果不明顯時可以嘗試用具體例子手動模擬過程來得出結(jié)論for(j=i-1;A[0].key<A[j].}插入類排序插入類排序就是在一個有序的序列中，插入一個新的關(guān)鍵字，直到所有的關(guān)鍵字都插入形成一上一節(jié)說的直接插入排序就是一種插入類排序。插入類排序還包括折半插入排序和希爾排序。折半插入排序直接插入排序是每次邊比較然后邊移動元素，直到找到插入的位置。折半插入排序?qū)⒈容^和移動這兩個操作分離出來，也就是先利用折半查找找到插入的位置，然后一次性移動元素，再插入該元素。值5第③次：i=3j=3,27>25,所以修改j=2,之間，也就是將13后面的元素都向后移動一位，騰出空位給25。插入25插入25值5for(i=2;i<=n;i++){//i記錄的是待插入的元素下標(biāo)，也就是說i-1之前的元素都是有序的//找到了待插入的位置接下來從后往前依次后移元素騰出位置for(j=i-1;j>=high+1;--j)A[jA[high+1]=A[0];//因為此時high指向的是待插入位置的前一位折半插入排序相比直接插入排序只是在尋找待插入位置時比較的次數(shù)減少(不是一個一個比較),每個待插入元素比較的次數(shù)大約在log?n(折半查找判定樹),所以n個元素比較low<high,就要不斷折半比較，折半一次比較一次。取決于表的長度n但是折半插入排序和直接插入排序在移動關(guān)鍵字的次數(shù)方面是一樣的(也就是說找到了具體的插入位置后，還是和直接插入排序一樣移動后面的關(guān)鍵字騰出空位)所以折半插穩(wěn)定性：和直接插入排序穩(wěn)定性相同，是穩(wěn)定的。希爾排序又稱為縮小增量排序希爾排序的基本思想：希爾排序本質(zhì)上還是插入排序，只不過是把待排序序列分成幾個子序列，再分按照一定增量(一組元素中下標(biāo)的差值)②縮小增量(d?=n/2,d+?=Ld/2),比如10個數(shù)據(jù)序列，第一次增量d?=10/2=5,第二次增量d?=③接下來的第三輪，第四輪…都是類似的過程，直到最后一輪以增量為1。此時就是前面所說的希爾排序的優(yōu)勢希爾排序的每一輪都會使整個序列變得越來越有序，最后一輪當(dāng)增量為1的時候，整個序列幾乎都是有序的，所以進(jìn)行直接插入排序會提高排序的效率。//初始增量為總長度的一半，之后依次除2且向下取整，//且最后一次要為1//果待插入的比有序序列最后一個小，則需要進(jìn)行排序(進(jìn)入if語句塊),如果大則不需要(跳出if語句塊)A[0]=A[]];//待插入關(guān)鍵字暫存在A[0]for(j=i-dkj>0&&A[0].key<A[j].k//待插入關(guān)鍵字之前以dk為增量的關(guān)鍵字只要比待插入關(guān)鍵字大的都往后移動dk位A[j+d]=A[O];//找到了待插入的位置，就將待插入關(guān)鍵字插入這個位置}}//且最后一次要為1for(j=i-dkj>0&&A[0].key<A[j].k//待插入關(guān)鍵字之前以dk為增量的關(guān)鍵字只要比待插入關(guān)鍵字大的都往后移動dk位A[j+d]=A[O];//找到了待插入的位}}時間復(fù)雜度：…希爾排序的時間復(fù)雜度約為O(n13)在最壞情況下希爾排序的時間復(fù)雜度為O(n2)希爾排序分析//對順序表作希爾插入排序，本算法和直接插入排序相比，作了以下修改：//1.前后記錄位置的增量是dk,不是1//2.r[0]只是暫存單元，不是哨兵，當(dāng)j<=0時，插入位置已到for(d=n/2;dk>=1;d?=d,/2)//初始增量為總長度的一半，之后依次除2且向下取整//果待插入的比有序序列最后一個小，則需要進(jìn)行排序(進(jìn)入if語句塊),如果大則不需要(跳出if語句塊)for(j=i-d,j>0&&A[0].key<A[j].k1.最后一趟的增量d,=11.最后一趟的增量d,=12.需要順序存儲結(jié)構(gòu)}穩(wěn)定性：不穩(wěn)定，由于不同的增量可能就會把相等的關(guān)鍵字劃分到兩個直接插入排序中進(jìn)行排序，可能就會造成相對順序變化。5223第一趟以2為增量排序后2253再以增量為1排序后2235換類排序快速排序冒泡排序假設(shè)待排序表長為n,從后往前(或從前往后)兩兩比較相鄰元素的值，若為逆序(即A[i-1]>A[])則交換它們，直到序列比較完。我們稱它為一趟冒泡，結(jié)果將最小的元素交換到待排序列的第一個位置。下一趟冒泡時，前一趟確定的最小元素不再參與比較，待排序列減少一個元素，每趟冒泡的結(jié)果把序列當(dāng)整個序列都有序的時候，標(biāo)志位是不發(fā)生修改的，從而表示已經(jīng)排好了for(j=n-1;j>ij--)//一趟冒泡過程if(A[j-1].key>A[j].key){//如果前面的元素比后面的大，則需要做交換flag=true;//發(fā)生了數(shù)據(jù)交換修改標(biāo)志位冒泡排序分析當(dāng)整個序列都有序的時候，標(biāo)志位是不發(fā)生修改的，從而表示已經(jīng)排for(j=n-1;j>i;j--)if(A[j-1].key>A[j].key){//如果前面的元素比后面的大，則需要做交換flag=true;//發(fā)生了數(shù)據(jù)交換修改標(biāo)志位f(flag==false)return;//本趟遍歷后沒有發(fā)生交換，說明表已經(jīng)有序}空間復(fù)雜度：交換時開辟了存儲空間來存儲中間變量，所以空間復(fù)雜度為O(1)時間復(fù)雜度：該算法基本操作是在于交換兩個數(shù)據(jù)。最壞情況下，初始序列就是逆序的，那么對于外層每一次循環(huán)，內(nèi)層循環(huán)始終成立，外層循環(huán)i從0最好情況下，初始序列就是順序的，內(nèi)層循環(huán)if條件始終不成立，所以內(nèi)層執(zhí)行n-1次后結(jié)束，所當(dāng)整個序列都有序的時候，標(biāo)志位是不發(fā)生修改的，從而表示已經(jīng)排好了//一趟冒泡過程//如果前面的元素比后面的大，則需要做交換flag=true;//發(fā)生了數(shù)據(jù)交換修改標(biāo)志位if(flag==false)return;//本趟遍歷后沒有發(fā)生交換，說明表已經(jīng)有序穩(wěn)定性：當(dāng)兩個關(guān)鍵字相等，if判斷條件不成立，所以不會發(fā)生數(shù)據(jù)移動。所以是穩(wěn)定的?？焖倥判蚴且环N基于分治法的排序方法。每一趟快排選擇序列中任一個元素作為快速排序是一種基于分治法的排序方法。每一趟快排選擇序列中任一個元素作為樞軸(pivot)(通常選第一個元素),將序列中比樞軸小的元素都移到樞軸前邊，比樞軸大的元素都快速排序結(jié)束。分治法：分治法：第一步首先將原問題分解成若干個子問題，這個子問題只是原問題較小規(guī)模遞歸地求解各子問題。遞歸的邊界就是問題規(guī)模足夠小的時候，可以直接求接下來分別對比46小的序列部分和比46大的序列部分進(jìn)行快比46大比46大A[low]=A[high];//用high的元素替換low的元素避免完全順序的序列出現(xiàn)數(shù)組下溢while(low<high&&A[ow]<=pivot)++low;//再從開頭往后找到第一個比樞軸大的元素A[high]=A[low避免完全順序的序列出現(xiàn)數(shù)組下溢}A[low]=pivot;//樞軸元素存放returnlow;}voidQuickSort(ElemTypeA[],i}時間復(fù)雜度：最好情況下時間復(fù)雜度為O(nlogn),待排序序列越無序，算法效率越高。最壞情況下時間復(fù)雜度為O(n2),待排序序列越有序，算法效率越低。遞歸復(fù)雜度的表達(dá)式：T(n)=aT(n/b)+f(n)n/b是子問題的大小，比如快排每次劃分子問題之后的大小，a是根據(jù)主定理的第二種情況(2)若f(n)=θ(nl?gb2),那么T(n)=e(rlogblogn)T(n)=O(nlogn)}時間復(fù)雜度：最好情況下時間復(fù)雜度為O(nlogn),待排序序列越無序，算法效率越高。最壞情況下時間復(fù)雜度為O(n2),待排序序列越有序，算法效率越低。遞歸復(fù)雜度的表達(dá)式：T(n)=aT(n/b)+f(n)n/b是子問題的大小，比如快排每次劃分子問題之后的大小，a是子問題大小的數(shù)量，f(n)是分解問題和合并問題所需要的時間2)快速排序最壞的情況就是每一次Partition取到的元素在一voidQuickSort(Elem}}時間復(fù)雜度：最好情況下時間復(fù)雜度為O(nlogn),待排序序列越無序，算法效率越高。最壞情況下時間復(fù)雜度為O(n2),待排序序列越有序，算法效率越低。相當(dāng)于每次都是將待排序列劃分為1個關(guān)鍵字和剩余其他關(guān)鍵字，n個關(guān)鍵字需要劃分n-1次，每次時間復(fù)雜度為O(n),所以最壞情況下時間復(fù)雜度為O(n2)voidQuickSort(ElemTypeA[],i}空間復(fù)雜度：由于快速排序是遞歸的，需要借助一個遞歸工作棧來保存每一層遞歸調(diào)用的必要信息，其容量應(yīng)與遞歸調(diào)用的最大深度一致。最壞情況下，因為要進(jìn)行n-1次遞歸調(diào)用，所以棧的深度為O(n);穩(wěn)定性：快速排序是不穩(wěn)定的，是因為存在交換關(guān)鍵字。對于522一趟快速排序之后225而且序列有序了所以最終也是225選擇類排序選擇排序：每一趟(例如第趟)在后voidSelectSort(ElemTypeA[],infor(i=0;i<n-1;i++){//依次從后面序列中選擇當(dāng)前最小的元素作為第i個元素最后一個元素不需要排序for(j=i+1;j<n;j++)//min存的是當(dāng)前最小元素所在下標(biāo)，初值設(shè)為第i個//從第i個元素往后找，一直要找到最后一個元素//如果這個值更小，則更新min值為這個更小的元素所在下標(biāo)//如果第i個元素不是剩下元素最小的，則和最小的進(jìn)行交換voidSelectSort(ElemTypeA[],infor(i=0;i<n-1;i++){//依次從后面序列中選擇當(dāng)前最小的元素作為第i個元素最后一個元素不需要排序//min存的是當(dāng)前最小元素所在下標(biāo)，初值設(shè)為第i個//如果這個值更小，則更新min值為這個更小的元素所在下標(biāo)//如果第i個元素不是剩下元素最小的，則和最小的進(jìn)行交換空間復(fù)雜度：需要額外的存儲空間僅為交換元素時借助的中間變量，所以空間復(fù)雜度是O(1)時間復(fù)雜度：關(guān)鍵操作在于交換元素操作，整個算法由雙重循環(huán)組成，外層循環(huán)從0到n-2一共n-2+1=n-1次，對于第i層外層循環(huán)，內(nèi)層循環(huán)執(zhí)行n-1-(i+1)+1=n-i-1次。1)(n-1)/2=n(n-1)/2,所以時間復(fù)雜度為O(n2)voidSelectSort(ElemTypeA[],infor(i=0;i<n-1;i++){//依次從后面序列中選擇當(dāng)前最小的元素作為第i個元素最后一個元素不需要排序//min存的是當(dāng)前最小元素所在下標(biāo)，初值設(shè)為第i個//如果這個值更小，則更新min值為這個更小的元素所在下標(biāo)//如果第i個元素不是剩下元素最小的，則和最小的進(jìn)行交換穩(wěn)定性：不穩(wěn)定原因就在于交換部分會打破相對順序i=0,min=2,交換5和22555和5的順序發(fā)生了變化堆排序什么是堆?堆是一棵完全二叉樹，而且滿足任何一個非葉結(jié)點的值都不大于(或不小于)其左右孩子結(jié)點的值。如果是每個結(jié)點的值都不小于它的左右孩子結(jié)點的值，則稱為大頂堆。如果是每個結(jié)點的值都不大于它的左右孩子結(jié)點的值，則稱為小頂堆。大頂堆小頂堆大頂堆什么是堆排序?所以堆排序的思想就是每次將無序序列調(diào)節(jié)成一個堆，然后從堆中選擇堆頂元素的值，這個值加入有序序列，無序序列減少一個，再反復(fù)調(diào)節(jié)無序序列，直到所有關(guān)鍵字都加入到有序序列。所以堆排序最重要的操作就是將無序序列調(diào)節(jié)成一個堆。(以大頂堆排序為例)調(diào)整方法：二叉樹由下至上由右至左(數(shù)組的下標(biāo)由大到小),檢查每個結(jié)點是否滿足大頂堆的要求，如果不滿足進(jìn)行調(diào)整。45234592四個結(jié)點都是葉子結(jié)點，不需要調(diào)整19<45<92,所以要用92和19進(jìn)行交換52>45且>23不需要調(diào)整原始序列堆排序①建堆：對初始序列的完全二叉樹調(diào)整成一個大頂堆調(diào)整方法：二叉樹由下至上由右至左(數(shù)組的下標(biāo)由大到小),檢查每個結(jié)點是否滿足大頂堆的要求，如果不滿足進(jìn)行調(diào)整。12<52<92要用92交換12堆排序①建堆：對初始序列的完全二叉樹調(diào)整成一個大頂堆調(diào)整方法：二叉樹由下至上由右至左(數(shù)組的下標(biāo)由大到小),檢查每個結(jié)點是否滿足大頂堆的要求，如果不滿足進(jìn)行調(diào)整。12<19<45要用45和12交換堆排序①建堆：對初始序列的完全二叉樹調(diào)整成一個大頂堆調(diào)整方法：二叉樹由下至上由右至左(數(shù)組的下標(biāo)由大到小),檢查每個結(jié)點是否滿足大頂堆的要求，如果不滿足進(jìn)行調(diào)整。到這里就建好了一個大頂堆②將堆頂結(jié)點和最后一個結(jié)點19交換也就是將最大值92移動到數(shù)組的最末尾有序序列中加入了結(jié)點92,無序序列減少結(jié)點92到這里堆排序的第一趟完成②將堆頂結(jié)點和最后一個結(jié)點19交換也就是將最大值92移動到數(shù)組的最末尾有序序列中加入了結(jié)點92,無序序列減少結(jié)點92到這里堆排序的第一趟完成堆排序③調(diào)堆：調(diào)整二叉樹的結(jié)點使得滿足大頂堆的要求。調(diào)整方法和建堆時一樣。45>12不需要調(diào)整，52也不需要19<45<52需要將結(jié)點19和52交換③調(diào)堆：調(diào)整二叉樹的結(jié)點使得滿足大頂堆的要求。調(diào)整方法和建堆時一樣。45>12不需要調(diào)整，52也不需要19<45<52需要將結(jié)點19和52交換19<23<45需要將結(jié)點19和45交換③調(diào)堆：調(diào)整二叉樹的結(jié)點使得滿足大頂堆的要求。調(diào)整方法和建堆時一樣。45>12不需要調(diào)整，52也不需要19<45<52需要將結(jié)點19和52交換19<23<45需要將結(jié)點19和45交換到這里又調(diào)成了一個大頂堆類似之前的操作，選出根結(jié)點52作為有序序列的第二個數(shù)值二叉樹性質(zhì)5:對完全二叉樹按從上到下、從左到右的順序依次編號1,2,…,N,則有以下關(guān)系：L7/2J=3,即下標(biāo)為3的位置存堆排序算法//開始檢查，直到根結(jié)點(注意根結(jié)點下標(biāo)不是0,是從1開始存儲)//如果發(fā)生交換，對交換過的結(jié)點繼續(xù)和它的孩子比較//如果這個結(jié)點的值不小于它的較大孩子結(jié)點值則不需要交換A[k]=A[0];//檢查到最后k的值就是最后一輪交換過的結(jié)點位置下標(biāo)將該結(jié)點換過去堆排序算法voidBuildMaxHeap(ElemTyp}voidAdjustDown(ElemTypeA[}}第一次調(diào)用AdjustDown,k=3,A[0]=A[3]=19,i=2*k=6,A[6]=45<A[7]=92,i=6+1=7for(i=len;i>1;i--){//n-1趟的交換和建堆過程空間復(fù)雜度：堆排序只需要在交換結(jié)點的時候需要額外存儲空間來輔佐，所以空間復(fù)雜度為O(1)時間復(fù)雜度：堆排序的總時間可以分為①建堆部分+②n-1次向下調(diào)整堆}}次數(shù)為}}//n-1趟的交換和建堆過程//輸出堆頂元素(和堆底元素交換)//把剩余的i-1個元素整理成堆根結(jié)點到葉子結(jié)點，完全二叉樹的高度為[log?(n+1)]所以時間復(fù)雜度為O(log?n)那么n-1個頂點時間復(fù)雜度為O(nlog?n)}}//n-1趟的交換和建堆過程時間復(fù)雜度：堆排序的總時間可以分為①建堆部分+②n-1次向下調(diào)整堆堆排序的時間復(fù)雜度為O(n)+O(nlog?n)=O(nlog?n)}//n-1趟的交換和建堆過程}穩(wěn)定性：右圖初始序列為122由于2在左孩子位置第一次交換之后2換到了堆頂所以2最終排好的位置在最后也就是122兩個2的位置發(fā)生了變化，所以堆排序不穩(wěn)定歸并排序假定待排序表含有n個記錄，則可以看成是n個有序的子表，每個子表長度為1,然后兩兩長度為n的有序表為止，這種排序方法稱為2-路歸并排序。①首先將整個序列的每個關(guān)鍵字看成一個單獨的有序的子序列②兩兩歸并，49和38歸并成{3849},65和97歸并成{6597},76和13歸并成{1376},27沒有歸并對象③兩兩歸并，{3849}和{6597}歸并成{38496597},{13,76}和27歸并成{132776}④兩兩歸并，{38496597}和{132776}歸并成{13273849657697}ElemType*B=(ElemType*)malloc((n+1)*sizeof(ElemType));//輔助數(shù)組B(動態(tài)分配內(nèi)存//表A的兩段A[low…mid]和A[mid+1…h(huán)igh]各自有序，將它們合并成一個有序表for(intk=low;k<=high;k++)B[k]=A[k];//將A中所有元素復(fù)制到B中;k++){k是歸并之后數(shù)組的下標(biāo)計數(shù)器//比較B的左右兩段中的元素//將較小值復(fù)制到A中//若第一個表未檢測完，直接將剩下的部分復(fù)制過來//若第二個表未檢測完，直接將剩下的部分復(fù)制過來}}1/從中間劃分兩個子序列//對左側(cè)子序列進(jìn)行遞歸排序//對右側(cè)子序列進(jìn)行遞歸排序//歸并4235423一共n個元素h所以n個元素調(diào)用「n/2h]次voidMergeSort(ElemTyp}}時間復(fù)雜度：一共n個元素第①趟Merge:一共n個元素列，每個子序列需要執(zhí)行1次Merge。Merge時間復(fù)雜度為子序列長度之和即2所以第①趟merge的時間復(fù)雜度為O(n/2*2)=O(n)n/4對第②趟Merge:子序列長度為4,所以有n/4n/4對列，每個子序列需要執(zhí)行1次Merge,Merge時間復(fù)雜度為子序列長度之和即4,所以第②趟merge的時間復(fù)雜度為O(n/4*4)=O(n)一共n個元素第①趟歸并：子序列長度為2,所以有n/2對子序列，每個子序列需要執(zhí)行1次Merge。Merge時間復(fù)雜度為子序列長度之和即2所以第①趟merge的時間復(fù)雜度為O(n/2*2)=O(n)第②趟歸并：子序列長度為4,所以有n/4對子序列，每個子序列需要執(zhí)行1次Merge,Merge時間復(fù)雜度為子序列長度之和即4,所以第②趟merge的時間復(fù)雜度為O(n/4*4)=O(n)當(dāng)n/2K=1時，k=log?n此時需要歸現(xiàn)整個序列有序。所以一共執(zhí)行了k=log?n趟排序，每趟排序的時間復(fù)雜度都是O(n)所以整個歸并排序的時間復(fù)雜度為O(nlog?n)歸并后3依然在3前面歸并后3依然在3前面空間復(fù)雜度：因為需要將這個待排序序列轉(zhuǎn)存到一個數(shù)組，所以需要額外開辟大小為n的存儲空間，即空間復(fù)雜度為O(n)穩(wěn)定性歸并前3在3前面1233445基數(shù)排序基數(shù)排序(也叫桶排序)是一種很特別的排序方法，它不是基于比較進(jìn)行排序的，而是采用多關(guān)鍵字排序思想(即基于關(guān)鍵字各位的大小進(jìn)行排序的),借助“分配”和“收集”兩種操作對單邏輯關(guān)鍵字進(jìn)行排序?；鶖?shù)排序又分為最高位優(yōu)先(MSD)排序和最低位優(yōu)先(LSD)排序。補(bǔ)充位數(shù)：053,003,542,748,014,214,154,063,616桶實際是一個隊列，先進(jìn)先出(從桶的上面進(jìn)，下面出)第一次“分配”(隊列從上入隊)桶2桶2桶5桶7桶0桶5桶7桶0第一次“收集”(隊列從下出隊)桶0桶1桶0542第二次“分配”桶0桶1桶0桶300桶3003053(隊列從上入隊)桶3桶4桶6桶5桶4桶6桶4桶5桶4基數(shù)排序第二次“收集”第三次“分配”桶4桶5542桶7桶9053214桶2桶3542桶5桶7桶8桶9063053桶0桶2桶3桶4桶5桶6桶7桶8桶9由于關(guān)鍵字現(xiàn)在三個數(shù)位都排列有序，所以整個關(guān)鍵字序列都排列有序。數(shù)據(jù)的種類，比如十進(jìn)制數(shù)字一共有0至9一共10個數(shù)字，即r=10空間復(fù)雜度：需要開辟關(guān)鍵字基的個數(shù)個隊列，所以空間復(fù)雜度為O(r)時間復(fù)雜度：需要進(jìn)行關(guān)鍵字位數(shù)d次"分配"和"收集",一次"分配"需要將n個關(guān)鍵字放進(jìn)各穩(wěn)定性：由于是隊列，先進(jìn)先出的性質(zhì)，所以在分配的時候是按照先后順序分配，也就是穩(wěn)定的，所以收集的時候也是保持穩(wěn)定的。即基數(shù)排序是穩(wěn)定的排序算法。桶0桶2桶3桶4桶5桶7桶9桶0對次高位進(jìn)行分配桶1桶2桶3桶5桶7桶8桶2桶5桶8桶9桶0桶3桶4桶6桶7桶2桶5桶8桶9桶0桶3桶4桶6桶7此時各個桶中都只有一個關(guān)鍵字，遞歸結(jié)束，收集各桶返回到上一層。此時桶中是這個樣子。桶5桶3桶4桶9桶0桶7桶8桶2桶5桶3桶4桶9桶0桶7桶8桶2桶0桶2桶3桶4桶5桶8桶9收集各桶：得到有序序列003014053063154214542616748外部排序截止目前學(xué)習(xí)過的所有排序算法，都是建立在計算機(jī)的內(nèi)存上進(jìn)行。由于內(nèi)存的大小限制，前面所學(xué)的排序算法都是針對數(shù)據(jù)量不是特別大的情況。所以這些排序都屬于內(nèi)部排序。但是很多時候，需要對大文件進(jìn)行排序，因為文件中的記錄很多、信息量龐大，無法將整個文件拷貝解決辦法：需要將待排序的記錄存儲在外存上，排序時再把數(shù)據(jù)一部分一部分的調(diào)入內(nèi)存進(jìn)行排序。在排序過程中需要多次進(jìn)行內(nèi)存和外存之間的交換，對外存文件中的記錄進(jìn)行排序后的結(jié)果仍然被放到原有文件中。這種排序的方法就叫做外部排序。三路歸并有序的歸并段1243454677多路歸并算法034670346246924694957內(nèi)存4957內(nèi)存多路歸并算法3467346424692469957內(nèi)存957內(nèi)存22多路歸并算法634763444469469957內(nèi)存957內(nèi)存通過多路歸并，就實現(xiàn)了在較小的內(nèi)存容量完成大規(guī)模的數(shù)據(jù)排序。一開始的這些有序的歸并段如何得到?當(dāng)然可以以單個數(shù)據(jù)為有序，然后一個一個數(shù)據(jù)調(diào)入內(nèi)存中進(jìn)行排序得到一些歸并段。但是帶來的開銷