計(jì)算機(jī)軟件及應(yīng)用數(shù)據(jù)結(jié)構(gòu)排序中國(guó)石油大學(xué)華東

1概述插入排序（直接、折半、希爾）快速排序交換排序（氣泡）選擇排序（直接）歸并排序第九章排序2排序算法的穩(wěn)定性:如果在元素序列中有兩個(gè)元素r[i]和r[j],它們的排序碼k[i]

==k[j]

,且在排序之前,元素r[i]排在r[j]前面。如果在排序之后,元素r[i]仍在元素r[j]的前面,則稱這個(gè)排序方法是穩(wěn)定的,否則稱這個(gè)排序方法是不穩(wěn)定的。內(nèi)排序與外排序:內(nèi)排序是指在排序期間數(shù)據(jù)元素全部存放在內(nèi)存的排序；外排序是指在排序期間全部元素個(gè)數(shù)太多，不能同時(shí)存放在內(nèi)存，必須根據(jù)排序過程的要求，不斷在內(nèi)、外存之間移動(dòng)的排序。39.2插入排序(InsertSorting)基本方法是：每步將一個(gè)待排序的元素，按其排序碼大小，插入到前面已經(jīng)排好序的一組元素的適當(dāng)位置上,直到元素全部插入為止?；舅枷胧?當(dāng)插入第i(i≥1)個(gè)元素時(shí)，前面的V[0],V[1],…,V[i-1]已經(jīng)排好序。這時(shí)，用V[i]的排序碼與V[i-1],V[i-2],…的排序碼順序進(jìn)行比較，后移，找到插入位置即將V[i]插入。9.2.1直接插入排序(InsertSort)4各趟排序結(jié)果21254925*1608012345012345temp21254925*160825i=1012345temp21254925*160849i=25012345i=4i=5i=3012345temp21254925*160816012345temp21254925*160825*012345temp21254925*1608086算法分析設(shè)待排序元素個(gè)數(shù)為currentSize=n,則該算法的主程序執(zhí)行n-1趟(第一個(gè)元素不用插入)。排序碼比較次數(shù)和元素移動(dòng)次數(shù)與元素排序碼的初始排列有關(guān)。最好情況下，排序前元素已按排序碼從小到大有序，每趟只需與前面有序元素序列的最后一個(gè)元素比較1次，總的排序碼比較次數(shù)為n-1,元素移動(dòng)次數(shù)為0。21254925*16080123457最壞情況下,第i趟時(shí)第i個(gè)元素必須與前面i個(gè)元素都做排序碼比較,并且每做1次比較就要做1次數(shù)據(jù)移動(dòng)。2125492816080123458平均情況下排序的時(shí)間復(fù)雜度為o(n2)。直接插入排序是一種穩(wěn)定的排序方法?；舅枷胧?設(shè)在順序表中有一個(gè)元素序列V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,V[i-1]是已經(jīng)排好序的元素。1)在插入V[i]時(shí),利用折半搜索法尋找V[i]的插入位置。2)找到位置后，再將插入位置之后的元素向后順次移動(dòng)。3)插入。折半插入排序(BinaryInsertsort)9算法分析折半搜索比順序搜索快,所以折半插入排序就平均性能來(lái)說(shuō)比直接插入排序要快。它所需的排序碼比較次數(shù)與待排序元素序列的初始排列無(wú)關(guān)，僅依賴于元素個(gè)數(shù)。折半插入排序是一個(gè)穩(wěn)定的排序方法。

10希爾排序方法又稱為縮小增量排序，基本思想是:1）選擇一個(gè)步長(zhǎng)序列d1，d2，…，dk，其中di>dj(i<j),dk=1；2）按步長(zhǎng)序列個(gè)數(shù)k，對(duì)序列進(jìn)行k趟排序；3）第I趟排序時(shí)，從第一個(gè)關(guān)鍵字開始，將間隔為di的關(guān)鍵字組成一個(gè)序列；從第二個(gè)關(guān)鍵字開始，將間隔為di的關(guān)鍵字組成一個(gè)序列；

……………………

從第di個(gè)關(guān)鍵字開始，將間隔為di的關(guān)鍵字組成一個(gè)序列分別對(duì)各序列進(jìn)行直接插入排序。4）重復(fù)上述步驟，僅步長(zhǎng)因子為1時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。9.2.3希爾排序(ShellSort)取d3=1三趟分組：1327485544938659776三趟排序：4132738484955657697例初始：4938659776132748554一趟排序：13

27

48

55

4

49

38

65

97

76二趟排序：13

4

48

38

27

49

55

65

97

76取d1=5一趟分組：49

38

65

97

76

13

27

48

55

4取d2=3二趟分組：13

27

48

55

4

49

38

65

97

7612算法分析：希爾排序是一種不穩(wěn)定的排序方法。Gap的取法有多種。最初shell提出取gap=

n/2

，gap=

gap/2

，直到gap=1。knuth提出取gap=

gap/3

+1。還有人提出都取奇數(shù)為好，也有人提出各gap互質(zhì)為好。想要弄清排序碼比較次數(shù)和元素移動(dòng)次數(shù)與增量選擇之間的依賴關(guān)系，并給出完整的數(shù)學(xué)分析，還沒有人能夠做到。13交換排序(ExchangeSort)基本思想是兩兩比較待排序元素的排序碼，如果發(fā)生逆序，則交換之。直到所有元素都排好序?yàn)橹?。思想：小的浮起，大的沉底。從左端開始比較。第一趟：第1個(gè)與第2個(gè)比較，大則交換；第2個(gè)與第3個(gè)比較，大則交換，……關(guān)鍵字最大的記錄交換到最后一個(gè)位置上；第二趟：對(duì)前n-1個(gè)記錄進(jìn)行同樣的操作，關(guān)鍵字次大的記錄交換到第n-1個(gè)位置上；依次類推，則完成排序。冒泡排序(BubbleSort)9854209854208959492909998542095848280888420589552045894402458922結(jié)果㈠㈡㈢㈣開始㈤024589比較次數(shù)：5432116基本思想：①任取待排序元素序列中的某個(gè)元素作為基準(zhǔn)（支點(diǎn)，一般去第一個(gè)），按照該元素的排序碼大小，將整個(gè)元素序列劃分為左右兩個(gè)子序列：左側(cè)子序列中所有元素的都小于基準(zhǔn)元素右側(cè)子序列中所有元素的都大于基準(zhǔn)元素②基準(zhǔn)元素則排在這兩個(gè)子序列中間(這也是該元素最終應(yīng)安放的位置)。③然后分別對(duì)這兩個(gè)子序列重復(fù)施行上述方法，直到所有的元素都排在相應(yīng)位置上為止。9.3快速排序(QuickSort)做法：附設(shè)兩個(gè)指針low和high

，初值分別指向第一個(gè)記錄和最后一個(gè)記錄，設(shè)支點(diǎn)記錄為r[1]

，(r[1]通常取第一個(gè)記錄的值為基準(zhǔn)值。)首先從high所指位置起向前搜索，找到第一個(gè)小于基準(zhǔn)值的記錄與基準(zhǔn)記錄交換（大的原地不動(dòng)），然后從low

所指位置起向后搜索，找到第一個(gè)大于基準(zhǔn)值的記錄與基準(zhǔn)記錄交換（小的原地不動(dòng)），重復(fù)這兩步直至low=high為止。例初始關(guān)鍵字：4938659776132750LHr[1].KEY=49HL

完成一趟排序：(273813)49(76976550)分別進(jìn)行快速排序:(13)

27

(38)49(5065)

76

(97)快速排序結(jié)束：13

27

3849

5065

76

974927LHLHLH4965HL1349LH4997LH199.4選擇排序基本思想是:首先從1~n個(gè)元素中選出關(guān)鍵字最小的記錄交換到第一個(gè)位置上。然后再?gòu)牡?個(gè)到第n個(gè)元素中選出次小的記錄交換到第二個(gè)位置上，依次類推。時(shí)間復(fù)雜度為O(n2)，適用于待排序元素較少的情況。20直接選擇排序(SelectSort)直接選擇排序的算法如下：voidSelectSort(STBLL[],intn){inti,j,k,t;for(i=0,i<n;++i）

{k=i；第I小的元素

for(j=i+1;j<n;++j)if(L[j].key<L[k].key)k=j;if(k!=i){t=L[i];L[i]=L[k];L[k]=t；}}}9.4.3堆排序(HeapSort)堆:是具有特定條件的順序存儲(chǔ)的完全二叉樹，其特定條件是：任何一個(gè)非葉子結(jié)點(diǎn)的關(guān)鍵字大于等于（或小于等于）子女的關(guān)鍵字的值。897624331510112536497856229.4.3堆排序(HeapSort)堆排序思想：設(shè)有n個(gè)元素，將其按關(guān)鍵字排序。首先將這n個(gè)元素按關(guān)鍵字建成堆，將堆頂元素輸出，得到n個(gè)元素中關(guān)鍵字最小(或最大)的元素。然后，再對(duì)剩下的n-1個(gè)元素建成堆，輸出堆頂元素，得到n個(gè)元素中關(guān)鍵字次小(或次大)的元素。如此反復(fù)，便得到一個(gè)按關(guān)鍵字有序的序列。稱這個(gè)過程為堆排序。堆排序分為兩個(gè)步驟:1）如何由一個(gè)無(wú)序序列建成一個(gè)堆？2）輸出堆頂元素后，如何將剩余元素調(diào)整成一個(gè)新的堆？23(1)第二個(gè)問題解決方法——篩選6525365649784111(b)65365649784111(c)251125365649784165(a)25493656657841(d)11方法：輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，并與其中小者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個(gè)從堆頂至葉子的調(diào)整過程為“篩選”24（2）第一個(gè)問題解決方法從無(wú)序序列的第

n/2個(gè)元素（即此無(wú)序序列對(duì)應(yīng)的完全二叉樹的最后一個(gè)非終端結(jié)點(diǎn)）起，至第一個(gè)元素止，進(jìn)行反復(fù)篩選2556497811654136(a)無(wú)序序列n=8,int(n/2)=4開始2556493611654178(b):78被篩選后的狀態(tài)2556413611654978(c):49被篩選后的狀態(tài)2511413656654978(d):56被篩選后的狀態(tài)(e):被篩選之后建成堆112541365665497825例含8個(gè)元素的無(wú)序序列（49，38，65，97，76，13，27，50）①先建成堆4965382713769750496538271376509749133827657650974913382765765097132738496576509726②進(jìn)行堆排序13273849657650979727384965765013輸出：132749389765765013輸出：139749382765765013輸出：13273849502765769713輸出：13276549502738769713輸出：132738274965502738769713輸出：1327387665502738499713輸出：132738495065762738499713輸出：132738499765762738495013輸出：13273849506597762738495013輸出：13273849509765762738495013輸出：132738495065287665972738495013輸出：1327384950659765762738495013輸出：132738495065769765762738495013輸出：1327384950657697299.5歸并排序(MergeSort)歸并，是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。把具有n個(gè)記錄的表看成是n個(gè)有序的子表，每個(gè)子表的長(zhǎng)度為1，然后兩兩歸并，得到[n/2]個(gè)長(zhǎng)度為2或?yàn)?的有序子表；再兩兩歸并，如此重復(fù)，直到得到一個(gè)長(zhǎng)度為n的有序表為止。初始序列[23][52][67][6][18][10]一趟歸并后[2352][667][1018]二趟歸并后[6235267][1018]三趟歸并后[61018235267]31迭代的歸并排序算法迭代的歸并排序算