數(shù)據(jù)結(jié)構(gòu)課件-第10章 排序

排序第10章10.1問題引入10.2插入排序10.3選擇排序10.4交換排序10.5歸并排序10.6基于比較排序的復(fù)雜度分析10.7基于分配的排序10.8索引排序*10.9拓展延伸*10.10應(yīng)用場景10.1問題引入10.1問題引入排序是指將數(shù)據(jù)按照關(guān)鍵字重新排列為升序（從小到大）或降序（從大到?。┑奶幚怼Ｉ颍宏P(guān)鍵字從小到大降序：關(guān)鍵字從大到小示例：

待排序列：341234’0896升序：081234’3496降序：963434’1208排序的穩(wěn)定性10.1問題引入若序列中關(guān)鍵字值相等的節(jié)點經(jīng)過某種排序方法進(jìn)行排序之后，仍能保持它們在排序前的相對順序，則稱這種排序方法是穩(wěn)定的；否則，稱這種排序方法是不穩(wěn)定的。穩(wěn)定的排序算法有：插入排序、冒泡排序、歸并排序不穩(wěn)定的排序算法：選擇排序、快速排序、堆排序示例：待排序列：穩(wěn)定：不穩(wěn)定：341234’0896081234

34’

96081234’

3496排序的分類10.1問題引入內(nèi)部排序、外部排序（根據(jù)內(nèi)存使用情況）內(nèi)部排序：數(shù)據(jù)存儲調(diào)整均在內(nèi)存中進(jìn)行外部排序：大部分節(jié)點在外存中，借助內(nèi)存進(jìn)行調(diào)整比較、分配（根據(jù)排序?qū)崿F(xiàn)手段）基于“比較”的排序：通過對關(guān)鍵字的比較，交換關(guān)鍵字在序列中的位置插入排序、冒泡排序、選擇排序、快速排序、歸并排序、希爾排序、堆排序基于“分配”的排序：通過將元素進(jìn)行分配和收集進(jìn)行排序基數(shù)排序、桶排序根據(jù)實現(xiàn)的難易程度：基本排序：插入排序、冒泡排序、選擇排序、……高級排序：快速排序、歸并排序、堆排序、基數(shù)排序、……10.2插入排序10.2插入排序基本思想:將一個記錄插入到已排好順序的序列中，形成一個新的、記錄數(shù)增1的有序序列折半插入排序和希爾排序是插入排序的兩種改進(jìn)直接插入排序希爾排序10.2.1直接插入排序10.2.1直接插入排序

直接插入排序過程10.2.1直接插入排序?qū)﹃P(guān)鍵字序列{68,65,84,65,83,84,82,85,67,84,85,82,69}進(jìn)行升序排列直接插入排序偽代碼10.2.1直接插入排序

1234567891011121314直接插入排序性能分析10.2.1直接插入排序

直接插入排序性能分析10.2.1直接插入排序

10.2.2折半插入排序10.2.2折半插入排序

10.2.3希爾排序10.2.3希爾排序

希爾排序偽代碼10.2.3希爾排序

1234567891012131415希爾排序過程10.2.3希爾排序

希爾排序性能分析10.2.3希爾排序

步長序列最壞情況下復(fù)雜度n

/2i(n2)2k

?1(n3/2)2i3i(nlog

2n)10.3選擇排序10.3選擇排序

10.3.1簡單選擇排序10.3.1簡單選擇排序簡單選擇排序在從待排序序列中選出鍵值最小的項時，所用的策略是簡單的逐個枚舉法。簡單選擇排序過程簡單選擇排序偽代碼10.3.1簡單選擇排序

1234567891011簡單選擇排序性能分析10.3.1簡單選擇排序

簡單選擇排序性能分析10.3.1簡單選擇排序

10.3.2堆排序10.3.2堆排序

初始堆建立過程10.3.2堆排序

（0）初始狀態(tài)（1）堆修復(fù)：無動作初始堆建立過程10.3.2堆排序

（2）堆修復(fù)：調(diào)整堆頂（3）堆修復(fù)：調(diào)整堆頂初始堆建立過程10.3.2堆排序

（4）堆修復(fù)：無動作（5）堆修復(fù)：調(diào)整堆頂和堆內(nèi)修復(fù)初始堆建立過程10.3.2堆排序

（6）堆修復(fù)：調(diào)整堆頂和堆內(nèi)修復(fù)（7）修復(fù)完成，獲得最終狀態(tài)堆排序過程10.3.2堆排序

（0）初始狀態(tài)（1）堆頂調(diào)整堆排序過程10.3.2堆排序

（3）堆頂調(diào)整堆排序過程10.3.2堆排序

堆排序偽代碼10.3.2堆排序

123456789堆排序性能分析10.3.2堆排序

10.4交換排序10.4交換排序數(shù)據(jù)結(jié)構(gòu)核心思路：對序列中的元素進(jìn)行多次兩兩交換，從而使序列元素有序。冒泡排序快速排序6865846583848285678485826968656765698482858484858283656567686768828283848485848582828484848585848484656567686982828384848485856865846583848285678485826965686584678384828569848582656568678469838482858284856565676869848283848285848565656768698284828384848585656567686982828483848485856565676869828283848484858565656768698282838484848585656567686982828384848485856565676869828283848484858565656768698282838484848585656567686982828384848485856565676869828283848484858510.4.1冒泡排序10.4.1冒泡排序數(shù)據(jù)結(jié)構(gòu)

冒泡排序示例數(shù)據(jù)結(jié)構(gòu)待排序數(shù)組第一輪第二輪第三輪第四輪第五輪第六輪第七輪第八輪第九輪第十輪第十一輪第十二輪68658465838482856784858269656865846783848285698485826565686784698384828582848565656768698482838482858485656567686982848283848485856565676869828284838484858565656768698282838484848585656567686982828384848485856565676869828283848484858565656768698282838484848585656567686982828384848485856565676869828283848484858565656768698282838484848585未排序已排序本輪排序10.4.1冒泡排序冒泡排序偽代碼10.4.1冒泡排序數(shù)據(jù)結(jié)構(gòu)1234567

冒泡排序性能分析10.4.1冒泡排序數(shù)據(jù)結(jié)構(gòu)

10.4.2快速排序10.4.2快速排序數(shù)據(jù)結(jié)構(gòu)快速排序是一種所需比較次數(shù)較少、速度較快的排序方法，由英國計算機(jī)科學(xué)家，圖靈獎獲得者東尼·霍爾于1961年發(fā)表。在基于比較的排序算法中，快速排序的平均性能突出?；舅枷耄和ㄟ^遞歸分治方法，基于軸點將待排序序列拆分成兩個子序列并分別排序，直到序列有序。排序步驟：從待排序序列中選取軸點。通過交換序列元素，將待排序序列拆分為左右兩個子序列，左子序列元素小于等于軸點，右子序列元素大于等于軸點。對兩個子序列遞歸進(jìn)行上述操作，直到子序列元素個數(shù)小于等于1?？焖倥判虻男蛄胁鸱?0.4.2快速排序數(shù)據(jù)結(jié)構(gòu)

快速排序的序列拆分10.4.2快速排序數(shù)據(jù)結(jié)構(gòu)

PartitionPartitionPartition

序列拆分示例10.4.2快速排序數(shù)據(jù)結(jié)構(gòu)

ij軸點4075344532781234’400123456775344532781234’40序列拆分示例10.4.2快速排序數(shù)據(jù)結(jié)構(gòu)

75344532781234’400123456775344532781234’40軸點40ij序列拆分示例10.4.2快速排序數(shù)據(jù)結(jié)構(gòu)

75344532781234’400123456775344532781234’40軸點40ij

序列拆分示例10.4.2快速排序數(shù)據(jù)結(jié)構(gòu)

34’344532781275400123456775344532781234’40軸點40ij

序列拆分示例10.4.2快速排序數(shù)據(jù)結(jié)構(gòu)

軸點40

i34’344532781275400123456775344532781234’40j序列拆分示例10.4.2快速排序數(shù)據(jù)結(jié)構(gòu)

軸點40

i34’341232784575400123456775344532781234’40j序列拆分示例10.4.2快速排序數(shù)據(jù)結(jié)構(gòu)

軸點40i34’341232784575400123456775344532781234’40j

序列拆分示例10.4.2快速排序數(shù)據(jù)結(jié)構(gòu)

軸點40i34’341232784575400123456775344532781234’40j

序列拆分示例10.4.2快速排序數(shù)據(jù)結(jié)構(gòu)

軸點40i34’341232404575780123456775344532781234’40j

快速排序示例10.4.2快速排序數(shù)據(jù)結(jié)構(gòu)

686584658384828567848582696865676569848285848485828365656768676882828384848584858282848484858584848465656768698282838484848585被選為軸點序列拆分后軸點所在位置序列拆分偽代碼10.4.2快速排序數(shù)據(jù)結(jié)構(gòu)

1234whiletruedo567891011121314151617181920快速排序偽代碼10.4.2快速排序數(shù)據(jù)結(jié)構(gòu)12345

快速排序性能分析10.4.2快速排序數(shù)據(jù)結(jié)構(gòu)

快速排序性能分析10.4.2快速排序數(shù)據(jù)結(jié)構(gòu)

快速排序性能分析10.4.2快速排序數(shù)據(jù)結(jié)構(gòu)

快速排序的軸點選擇10.4.2快速排序數(shù)據(jù)結(jié)構(gòu)

10.5歸并排序10.5歸并排序數(shù)據(jù)結(jié)構(gòu)核心思路：基于分治思想，將兩個或兩個以上的有序序列合并為一個新的有序序列。歸并次序：自頂向下：將序列拆分直到有序；然后使用歸并算法得到排序結(jié)果。自底向上：將序列看成多條有序子序列，并將子序列兩兩合并。應(yīng)用場景：求逆序數(shù)對：通過歸并排序，快速計算序列中逆序數(shù)對的數(shù)量。10.5.1二路歸并10.5.1二路歸并數(shù)據(jù)結(jié)構(gòu)

二路歸并偽代碼10.5.1二路歸并數(shù)據(jù)結(jié)構(gòu)12345678910111213

10.5.2歸并排序10.5.2歸并排序數(shù)據(jù)結(jié)構(gòu)利用上述歸并思想和二路歸并算法來實現(xiàn)的排序算法稱為歸并排序。算法首先將序列拆分，直到被拆分的子序列長度為1，此時子序列顯然有序。然后，使用上述二路歸并算法，將有序的短序列依次合并為長序列，最終完成序列的排序。據(jù)歸并時對子序列劃分方式的不同，歸并排序算法又可分為自頂向下和自底向上兩種。自頂向下歸并排序示例10.5.2歸并排序數(shù)據(jù)結(jié)構(gòu)自頂向下歸并排序偽代碼10.5.2歸并排序數(shù)據(jù)結(jié)構(gòu)123456

自底向上歸并排序示例10.5.2歸并排序數(shù)據(jù)結(jié)構(gòu)自底向上歸并排序偽代碼10.5.2歸并排序數(shù)據(jù)結(jié)構(gòu)

歸并排序性能分析10.5.2歸并排序數(shù)據(jù)結(jié)構(gòu)

歸并排序的改進(jìn)10.5.2歸并排序數(shù)據(jù)結(jié)構(gòu)

改進(jìn)后二路歸并的偽代碼10.5.2歸并排序數(shù)據(jù)結(jié)構(gòu)1234567891011121314

改進(jìn)后自底向上歸并排序的偽代碼10.5.2歸并排序數(shù)據(jù)結(jié)構(gòu)

sorted_len←1//當(dāng)前有序子列長度n←r-l+1//待排元素個數(shù)，即序列長度count←0while

sorted_len<n

do//當(dāng)前有序子列長度小于序列長度，則相鄰兩子序列歸并|count←count+1|lx←l//左子序列從最左端開始|while

lx≤r-sorted_len

do||rx←lx+sorted_len-1//左子序列的右端點||ry←Min(rx+sorted_len,r)//右子序列的右端點||ifcount%2=1then|||TwoWayMergeImproved(a,t,lx,rx,ry)//a并入t||else|||TwoWayMergeImproved(t,a,lx,rx,ry)//t并入a||end||lx←ry+1//下一對子序列的左子序列的左端點|end|sorted_len←sorted_len×2//有序子列長度加倍end求逆序?qū)?shù)量10.5.2歸并排序數(shù)據(jù)結(jié)構(gòu)

求逆序?qū)?shù)量10.5.2歸并排序數(shù)據(jù)結(jié)構(gòu)

求逆序?qū)?shù)量10.5.2歸并排序數(shù)據(jù)結(jié)構(gòu)

二路歸并求逆序?qū)p量的偽代碼10.5.2歸并排序數(shù)據(jù)結(jié)構(gòu)

123456789101112131415歸并排序兼求逆序?qū)?shù)量的偽代碼10.5.2歸并排序數(shù)據(jù)結(jié)構(gòu)

1234567810.6基于比較排序的復(fù)雜度分析10.6基于比較排序的復(fù)雜度分析數(shù)據(jù)結(jié)構(gòu)

10.6.1基于比較的排序的復(fù)雜度下界10.6.1基于比較的排序的復(fù)雜度下界數(shù)據(jù)結(jié)構(gòu)

10.6.1基于比較的排序的復(fù)雜度下界10.6.1基于比較的排序的復(fù)雜度下界數(shù)據(jù)結(jié)構(gòu)

10.6.1基于比較的排序的復(fù)雜度下界10.6.1基于比較的排序的復(fù)雜度下界數(shù)據(jù)結(jié)構(gòu)

10.6.2基于比較的排序的平均復(fù)雜度10.6.2基于比較的排序的平均復(fù)雜度數(shù)據(jù)結(jié)構(gòu)

10.6.3最少比較排序10.6.3最少比較排序數(shù)據(jù)結(jié)構(gòu)

331616333455191937387722224142101026264546131329304950[1]StoberF,Wei?A.LowerBoundsforSorting16,17,and18Elements[C]//2023ProceedingsoftheSymposiumonAlgorithmEngineeringandExperiments(ALENEX).SocietyforIndustrialandAppliedMathematics,2023:201-213.

10.6.3最少比較排序10.6.3最少比較排序數(shù)據(jù)結(jié)構(gòu)

[1]FordLR,JohnsonSM.ATournamentProblem[J].AmericanMathematicalMonthly,1959,66(5):387-389.DOI:10.2307/2308750.10.7基于分配的排序10.7基于分配的排序數(shù)據(jù)結(jié)構(gòu)定義：不基于“比較-移動”的排序方式，常見的基于分配的排序有計數(shù)排序（Counting

Sort）桶排序（BucketSort）基數(shù)排序（Radix

Sort）10.7.1計數(shù)排序10.7.1計數(shù)排序數(shù)據(jù)結(jié)構(gòu)

初始狀態(tài)統(tǒng)計每個值出現(xiàn)的次數(shù)10.7.1計數(shù)排序10.7.1計數(shù)排序數(shù)據(jù)結(jié)構(gòu)

統(tǒng)計cnt前綴和從后向前依次將A的每個元素x放入B中，具體位置由cnt[x]確定10.7.1計數(shù)排序10.7.1計數(shù)排序數(shù)據(jù)結(jié)構(gòu)

插入3插入410.7.1計數(shù)排序10.7.1計數(shù)排序數(shù)據(jù)結(jié)構(gòu)

插入3插入剩余的元素計數(shù)排序偽代碼10.7.1計數(shù)排序數(shù)據(jù)結(jié)構(gòu)

b←newElemSet[r-l+1]//臨時存放有序序列的數(shù)組cnt←newint[k+1]()//計數(shù)數(shù)組，初始全零for

i←l

to

r

do|cnt[ai]←cnt[ai]+1endfor

i←1to

k

do|cnt[i]←cnt[i-1]+cnt[i]endfor

i←r

downtol

do|p←cnt[ai]//ai

應(yīng)該在b中的位置|bp←ai//將ai放入|cnt[ai]←cnt[ai]-1endfor

i←l

to

r

do//將有序的b放回a中|ai←bi-l+1end計數(shù)排序性能分析10.7.1計數(shù)排序數(shù)據(jù)結(jié)構(gòu)

計數(shù)排序是穩(wěn)定的。“特殊的”計數(shù)排序——桶排序10.7.1計數(shù)排序數(shù)據(jù)結(jié)構(gòu)

桶排序性能分析10.7.1計數(shù)排序數(shù)據(jù)結(jié)構(gòu)

桶排序是穩(wěn)定的。10.7.2基數(shù)排序10.7.2基數(shù)排序數(shù)據(jù)結(jié)構(gòu)

基數(shù)排序中的計數(shù)排序偽代碼10.7.2基數(shù)排序數(shù)據(jù)結(jié)構(gòu)

for

i←r

downtol

do|p←cnt[ci]//ai

應(yīng)該在b中的位置|bp←ai//將ai放入|cnt[ci]←cnt[ci]-1endfor

i←l

to

r

do//將有序的b放回a中|ai←bi-l+1endreturn

cnt最高位優(yōu)先基數(shù)排序10.7.2基數(shù)排序數(shù)據(jù)結(jié)構(gòu)

初始狀態(tài)以百位劃分子序列以十位劃分子序列以個位劃分子序列最高位優(yōu)先基數(shù)排序偽代碼10.7.2基數(shù)排序數(shù)據(jù)結(jié)構(gòu)

1234567最低位優(yōu)先基數(shù)排序10.7.2基數(shù)排序數(shù)據(jù)結(jié)構(gòu)

初始狀態(tài)按個位進(jìn)行排序按十位進(jìn)行排序按百位進(jìn)行排序最低位優(yōu)先基數(shù)排序偽代碼10.7.2基數(shù)排序數(shù)據(jù)結(jié)構(gòu)

123基數(shù)排序性能分析10.7.2基數(shù)排序數(shù)據(jù)結(jié)構(gòu)

10.8索引排序10.8索引排序數(shù)據(jù)結(jié)構(gòu)

基于插入排序的索引排序的偽代碼10.8索引排序數(shù)據(jù)結(jié)構(gòu)

for

i←l+1to

r

do|t←idxi|for

j←i-1downto

ldo||if

aidxj>at

then|||idxj+1←idxj||else|||idxj+1←t|||break||end|end|if

aidxl>at

then||idxl←t|endendreturn

idx元素順序調(diào)整10.8索引排序數(shù)據(jù)結(jié)構(gòu)

元素順序調(diào)整的偽代碼10.8索引排序數(shù)據(jù)結(jié)構(gòu)

for

i←l+1to

r

do|t←idxi|for

j←i-1downto

ldo||if

aidxj>at

then|||idxj+1←idxj||else|||idxj+1←t|||break||end|end|if

aidxl>at

then||idxl←t|endendreturn

idx10.9拓展延伸10.9拓展延伸數(shù)據(jù)結(jié)構(gòu)前面幾節(jié)介紹了經(jīng)典排序算法的原理和特點。本節(jié)從庫函數(shù)實現(xiàn)的角度，介紹兩個拓展算法：內(nèi)省排序：C++語言中最常用的排序函數(shù)實現(xiàn)時采用的排序算法，它是快速排序的一種拓展，是以快速排序為主干，混合堆排序和插入排序的一種混合排序算法；蒂姆排序：Java和Python語言中最常用的排序函數(shù)實現(xiàn)時采用的排序算法，它是歸并排序的一種拓展，主要思想是對序列中的有序（順序或逆序）子序列進(jìn)行利用以提高效率，同時混合了插入排序作為優(yōu)化。10.9.1內(nèi)省排序10.9.1內(nèi)省排序數(shù)據(jù)結(jié)構(gòu)

內(nèi)省排序的偽代碼10.9.1內(nèi)省排序數(shù)據(jù)結(jié)構(gòu)

1234567891010.9.2蒂姆排序10.9.2蒂姆排序數(shù)據(jù)結(jié)構(gòu)蒂姆排序：蒂姆排序是一種混合、穩(wěn)定的自適應(yīng)排序算法，其結(jié)合了歸并排序和插入排序的思想，旨在對真實情況下的數(shù)據(jù)有更好的排序效率。蒂姆排序由

TimPeters

在

2002

年提出，并自

Python2.3

版本以來，一直作為其標(biāo)準(zhǔn)排序算法，并且在

JavaSE7、Swift

和

Rust

等語言中，使用它對非原始類型的數(shù)組進(jìn)行排序。蒂姆排序的基本思想是：先找到輸入數(shù)據(jù)中的有序連續(xù)子序