計算機軟件及應用數(shù)據(jù)結構排序中國石油大學華東

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

==k[j]

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

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

……………………

從第di個關鍵字開始，將間隔為di的關鍵字組成一個序列分別對各序列進行直接插入排序。4）重復上述步驟，僅步長因子為1時，整個序列作為一個表來處理，表長度即為整個序列的長度。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互質為好。想要弄清排序碼比較次數(shù)和元素移動次數(shù)與增量選擇之間的依賴關系，并給出完整的數(shù)學分析，還沒有人能夠做到。13交換排序(ExchangeSort)基本思想是兩兩比較待排序元素的排序碼，如果發(fā)生逆序，則交換之。直到所有元素都排好序為止。思想：小的浮起，大的沉底。從左端開始比較。第一趟：第1個與第2個比較，大則交換；第2個與第3個比較，大則交換，……關鍵字最大的記錄交換到最后一個位置上；第二趟：對前n-1個記錄進行同樣的操作，關鍵字次大的記錄交換到第n-1個位置上；依次類推，則完成排序。冒泡排序(BubbleSort)9854209854208959492909998542095848280888420589552045894402458922結果㈠㈡㈢㈣開始㈤024589比較次數(shù)：5432116基本思想：①任取待排序元素序列中的某個元素作為基準（支點，一般去第一個），按照該元素的排序碼大小，將整個元素序列劃分為左右兩個子序列：左側子序列中所有元素的都小于基準元素右側子序列中所有元素的都大于基準元素②基準元素則排在這兩個子序列中間(這也是該元素最終應安放的位置)。③然后分別對這兩個子序列重復施行上述方法，直到所有的元素都排在相應位置上為止。9.3快速排序(QuickSort)做法：附設兩個指針low和high

，初值分別指向第一個記錄和最后一個記錄，設支點記錄為r[1]

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

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

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

27

(38)49(5065)

76

(97)快速排序結束：13

27

3849

5065

76

974927LHLHLH4965HL1349LH4997LH199.4選擇排序基本思想是:首先從1~n個元素中選出關鍵字最小的記錄交換到第一個位置上。然后再從第2個到第n個元素中選出次小的記錄交換到第二個位置上，依次類推。時間復雜度為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)堆:是具有特定條件的順序存儲的完全二叉樹，其特定條件是：任何一個非葉子結點的關鍵字大于等于（或小于等于）子女的關鍵字的值。897624331510112536497856229.4.3堆排序(HeapSort)堆排序思想：設有n個元素，將其按關鍵字排序。首先將這n個元素按關鍵字建成堆，將堆頂元素輸出，得到n個元素中關鍵字最小(或最大)的元素。然后，再對剩下的n-1個元素建成堆，輸出堆頂元素，得到n個元素中關鍵字次小(或次大)的元素。如此反復，便得到一個按關鍵字有序的序列。稱這個過程為堆排序。堆排序分為兩個步驟:1）如何由一個無序序列建成一個堆？2）輸出堆頂元素后，如何將剩余元素調(diào)整成一個新的堆？23(1)第二個問題解決方法——篩選6525365649784111(b)65365649784111(c)251125365649784165(a)25493656657841(d)11方法：輸出堆頂元素之后，以堆中最后一個元素替代之；然后將根結點值與左、右子樹的根結點值進行比較，并與其中小者進行交換；重復上述操作，直至葉子結點，將得到新的堆，稱這個從堆頂至葉子的調(diào)整過程為“篩選”24（2）第一個問題解決方法從無序序列的第

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