《計算機應(yīng)用基礎(chǔ)》1.6 排序

第1章數(shù)據(jù)結(jié)構(gòu)

主要內(nèi)容1.1基本數(shù)據(jù)結(jié)構(gòu)與算法

1.2線性表1.3棧和隊列1.4樹和二叉樹

1.5查找1.6排序ABCDEFG姓名學(xué)號成績班級李紅976105995機97.6

1065865編輯ppt1.6排序排序又稱分類，是計算機程序設(shè)計中一個重要運算，它的功能是將一組任意序列的數(shù)據(jù)元素，進行按關(guān)鍵字由大到小的順序（降序）排列或按由小到大的順序（升序）排列。排序的對象：這些數(shù)據(jù)元素可以是數(shù)值型，也可以為字符型。若為數(shù)值型，則按數(shù)值大小排列；若為字符型，則按其ASCII碼的順序排列。排序的依據(jù)：在實際應(yīng)用中，參加排序的數(shù)據(jù)元素有時不是單個數(shù)據(jù)項，而是由多個數(shù)據(jù)項組成的記錄。此時排序應(yīng)按照關(guān)鍵字的大小進行。所謂關(guān)鍵字是指記錄中的某個數(shù)據(jù)項，用它可以標(biāo)識一個記錄。若此關(guān)鍵字可以唯一地標(biāo)識一個記錄，則稱此關(guān)鍵字為主關(guān)鍵字；反之，把用以識別若干記錄的關(guān)鍵字稱為次關(guān)鍵字。

學(xué)號姓名系別住址電話981111李洪機械六舍5371111982111王剛電子四舍5372111983211王將計算機五舍5373211983212張強機械六舎5372221編輯ppt排序的穩(wěn)定性：在待排序的記錄中，若存在多個關(guān)鍵在相同的記錄，經(jīng)過排序后，這些具有相同關(guān)鍵在的記錄之間的相對次序發(fā)生變化，則稱這種排序方法是穩(wěn)定的；否則，是不穩(wěn)定的。排序的分類：內(nèi)部排序與外部排序內(nèi)部排序:整個排序過程完全在內(nèi)存中進行.外部排序:由于待排序記錄數(shù)據(jù)量太大,內(nèi)存無法容納全部數(shù)據(jù),排序需要借助外部存儲設(shè)備才能完成.排序算法評價：算法執(zhí)行時間(最好、最差及平均情況)、需要附加空間大小1.6排序編輯ppt插入排序的基本思想：1.6.2插入排序插入排序三種方法1.直接排序:

認可第1個記錄已排好序，然后將第2個到第n個記錄依次插入到前面已排好序的記錄組成的文件中。2.折半插入排序:折半插入排序在尋找插入位置時，不是逐個比較而是利用折半查找的原理尋找插入位置。待排序元素越多，改進效果越明顯。3.希爾排序:將整個無序序列分割成若干個子序列分別進行直接插入排序.將待排序文件中的記錄，逐個按其排序碼值的大小插入到已排好序的若干個記錄組成的文件中的適當(dāng)位置，保持新文件有序。

編輯ppt1.直接插入排序:

思路：認可第1個記錄已排好序，然后將第2個到第n個記錄依次插入到前面已排好序的記錄組成的文件中。具體過程(第i個記錄Ri插入到前面i-1個已排好序的記錄中)

將Ri的排序碼與前面已排好序的排序碼從右向左依次比較，找到Ri應(yīng)插入的位置；將該位置以后直到Ri-1各記錄順序后移,空出位置插入Ri。1.6.2插入排序編輯ppt<例>直接插入排序:次數(shù)ir[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]r[8]

(49)39669676113750

(3949)669676113750i=239(394966)9676113750i=366(39496696)76113750i=496(3949667696)113750i=576(113949667696)3750i=611(11373949667696)50i=737(1137394950667696)

i=850對于有n個數(shù)據(jù)元素的待排序列，插入操作要進行n-1次編輯ppt............./*對N個整數(shù)進行升序排序*/for(i=1;i<N;i++){

for(k=i-1;k>=0;k--)//尋找插入位置 if(a[i]>a[k]) break;//插入到第k個位置的后面

temp=a[i];

for(j=i-1;j>k;j--)//向后移動 a[j+1]=a[j];

a[j+1]=temp;}編輯ppt............./*改進前面的算法*/for(i=1;i<N;i++){/*一邊比較，一邊移動*/

temp=a[i];

for(j=i-1;j>=0&&temp<a[j];j--)

a[j+1]=a[j];

a[j+1]=temp;}temp>a[j]若降序排序，則：編輯ppt1.直接插入排序:

時效分析最好情況:初始排序碼已經(jīng)有序。共比較n-1次，移動0次。最壞情況:待排序序列完全逆序。比較和移動均為n(n-1)/2次。平均情況:比較和移動次數(shù)均約為n2/4，時間復(fù)雜度為O(n2)。1.6.2插入排序該算法適合于n較小的情況，時間復(fù)雜度為O(n2).編輯ppt2、折半插入排序

折半插入排序在尋找插入位置時，不是逐個比較而是利用折半查找的原理尋找插入位置。待排序元素越多，改進效果越明顯。例：有6個記錄，前5個已排序的基礎(chǔ)上，對第6個記錄排序。[1527365369]42

lowmidhigh

(42>36,后半)[1527365369]

42

lowhigh

mid

(42<53,前半)

[1527365369]42

highlow(high<low，查找結(jié)束，插入位置為low或high+1)[152736425369]

折半插入排序減少了關(guān)鍵字的比較次數(shù)，但記錄的移動次數(shù)不變，其時間復(fù)雜度與直接插入排序相同為O(n2)。1.6.2插入排序編輯ppt3.希爾排序基本思想：將整個無序序列分割成若干個子序列分別進行直接插入排序,待整個序列中的記錄”基本有序”時,再對全體記錄進行一次直接插入排序。子序列分割：選定兩個元素之間距離h，將所有間隔為h的元素分成一組(將相隔某個增量h的元素構(gòu)成一個子系列)具體實現(xiàn):

(1)選擇一個增量序列t1，t2，…，tk,其中ti>tj,tk=1。(2)按增量序列個數(shù)k，對序列進行k趟排序。(3)每趟排序，根據(jù)對應(yīng)的增量ti，將序列分割成若干長度為m的子序列，分別對各子表直接插入排序。增量ti逐次減小，tk=1時，再對全部元素進行一次直接插入排序即可完成。1.6.2插入排序編輯ppt舉例:有一個含有14個數(shù)的序列,使用希而排序進行升序排序(39,80,76,41,13,29,50,78,30,11,100,7,41,86)取增量：5，3，1h=53980764113295078301110074186(R1,R6,R11)3929100(R2,R7,R12)

80507(R3,R8,R13)

767841(R4,R9,R14)

413086(R5,R10)

1311則子序列：{39，29，100}，{80，50，7}，{76，78，41}，{41，30，86}，{13，11}R1,R2,R3,R4,R5,R6,R7,R8,R9,R10R11,R12,R13,R14編輯ppth=53980764113295078301110074186子序列：{39，29，100}，{80，50，7}，{76，78，41}，{41，30，86}，{13，11}R1,R2,R3,R4,R5,R6,R7,R8,R9,R10R11,R12,R13,R14

293910075080

41767830418611

13因此第一趟排序結(jié)果如下:

2974130113950764113100807886對每個序列進行直接插入排序:編輯ppth=3

29741301139507641131008078862930501378

7117610086

41394180分別對以上3個子序列,即{29，30，50，13，78}，{7，11，76，100，86}，{41，39，41，80}進行直接插入排序,1373929114130764150868078100(R1,R4,R7,R10,R13)(R2,R5,R8,R11,R14)(R3,R6,R9,R12)R1R2R3R4R5R6R7R8R9R10R11R12R13R1413293050787117686100

39

414180第二趟最終結(jié)果：第一趟排序結(jié)果編輯ppt1373929114130764150868078100h=1

序列基本有序，對其進行直接插入排序,第三趟最終結(jié)果：7111329303941415076788086100第二趟最終結(jié)果：編輯ppt3.希爾排序特點：每一遍以不同間隔距離插入排序。h較大時移動數(shù)據(jù)元素是跳躍式進行。子序列每一次比較可能移去多個逆序(直接插入排序每次比較只能移去一個)。效率較高。最后一次排序(h=1)時，已基本有序，不需要多少移動。故其時間復(fù)雜度較直接插入排序低。數(shù)學(xué)難題：如何選取增量序列才能有最好的排序效果，至今未完整解決。但注意：增量序列中除1外沒有公因子，且最后一個增量序列必須為1。時效分析:很難。比較次數(shù)與移動次數(shù)依賴于增量序列的選取，特定情況下可以估計.1.6.2插入排序編輯ppt對待排序記錄兩兩比較排序碼，不滿足排序順序則交換。直到任何兩個記錄排序碼滿足排序要求。基本思路交換排序種類:冒泡排序快速排序

1.6.3交換排序編輯ppt1.冒泡排序基本思想：通過相鄰元素的交換，逐步將線性表變成有序。基本過程：第一趟冒泡排序：首先第一個元素與第二個元素比較，逆序則交換；然后第二個元素與第三個元素比較；直到第n-1個元素與第n個元素比較為止。結(jié)果（關(guān)鍵字）最大的元素放在最后位置。第二趟冒泡排序：對前面n-1個元素進行相同操作，結(jié)果

次大元素放在n-1位置上。第i趟冒泡排序：對前面n-i+1個元素進行相同操作，結(jié)果(n-i+1)中最大元素放在(n-i+1)位置上。趟數(shù)：最多n-1

結(jié)束條件：在某一趟排序中沒有進行交換元素操作。1.6.3交換排序編輯ppt<例>3849657613273097第一趟38496513273076第二趟384913273065第三趟3813273049第四趟13273038第五趟132730第六趟4938659776132730初始關(guān)鍵字n=8384976971397279730971376767627301365276530651313494930492738273830381327第七趟思想：小的浮起，大的沉底。編輯ppt舉例:將數(shù)列(8,6,5,7,1)升序排序初始86571第一趟65718第二趟56178第三趟51678第四趟15678初始已排好序(正序最好)，則只需進行一趟排序,比較次數(shù)n-1，移動次數(shù)為0。逆序(最壞)，則需進行n-1趟排序,比較次數(shù)為(1+2+3+…+n-1)=n(n-1)/2。是穩(wěn)定的排序,時間復(fù)雜度為O(n2),空間復(fù)雜度是O(1).時效分析:程序代碼:編輯ppt#defineN5……intgrade[N],temp;for(i=0;i<N;i++)scanf("%d",&grade[i]);for(i=0;i<N-1;i++){for(j=0;j<N-1-i;j++){ if(grade[j]>grade[j+1]) { temp=grade[j+1]; grade[j+1]=grade[j]; grade[j]=temp; }}}……讀入5個值保存在數(shù)組中1671469085編輯ppttemp=46temp=71temp=161671469085i=0第1趟j=0從頭開始比較j<4條件不成立j=1j<4條件成立9046j=2j<4條件成立9071j=3j<49016j=4內(nèi)層循環(huán)終止90即：i=0第1趟時grade[0]和grade[1]比較grade[1]和grade[2]比較grade[2]和grade[3]比較grade[3]和grade[4]比較最大值放到grade[4]中#defineN5……for(i=0;i<N-1;i++){for(j=0;j<N-1-i;j++){ if(grade[j]>grade[j+1]) { temp=grade[j+1]; grade[j+1]=grade[j]; grade[j]=temp; }}}……即，i=0第1趟時內(nèi)存循環(huán)for(j=0;j<N-1-i;j++)變量j是從0到3的編輯ppt1671469085i=1第2趟j=0從頭開始比較90469071901690#defineN5……for(i=0;i<N-1;i++){for(j=0;j<N-1-i;j++){ if(grade[j]>grade[j+1]) { temp=grade[j+1]; grade[j+1]=grade[j]; grade[j]=temp; }}}……內(nèi)存循環(huán)for(j=0;j<N-1-i;j++)中j的取值從0到2grade[0]和grade[1]比較grade[1]和grade[2]比較grade[2]和grade[3]比較找出次大值放到grade[3]中編輯ppt1671469085i=1第2趟9046907190169085468571851685#defineN5……for(i=0;i<N-1;i++){for(j=0;j<N-1-i;j++){ if(grade[j]>grade[j+1]) { temp=grade[j+1]; grade[j+1]=grade[j]; grade[j]=temp; }}}……編輯ppt16714685i=2第3趟9046907190169085468571851685717116#defineN5……for(i=0;i<N-1;i++){for(j=0;j<N-1-i;j++){ if(grade[j]>grade[j+1]) { temp=grade[j+1]; grade[j+1]=grade[j]; grade[j]=temp; }}}……編輯ppt16714685i=3第4趟9046907190169085468571851685717116#defineN5……for(i=0;i<N-1;i++){for(j=0;j<N-1-i;j++){ if(grade[j]>grade[j+1]) { temp=grade[j+1]; grade[j+1]=grade[j]; grade[j]=temp; }}}……461646編輯ppt2.快速排序基本思想：

通過一趟排序?qū)⒋庞涗浄指畛瑟毩刹糠郑渲幸徊糠钟涗浀年P(guān)鍵字均比另一部分記錄的關(guān)鍵字小，再對前、后兩部分待排記錄重復(fù)上述過程，直到所有子表表長不超過1為止。優(yōu)點：

通過兩個不相鄰元素交換，可以一次交換消除多個逆序，加快排序速度。

4939669676112750[273911]49[76

966650]

2739

49[5066]7696

1.6.3交換排序編輯ppt2.快速排序過程:

首先任選一個記錄K(通常選第一個記錄)作為樞軸(支點)附設(shè)兩個指針i和j分別指向第一個記錄和最后一個記錄。(1)指針j向前搜索逐個記錄與K比較,直到發(fā)現(xiàn)小于K的記錄為止，將其與樞軸記錄互相交換。(2)指針i向后搜索逐個記錄與K比較,直到發(fā)現(xiàn)大于K的記錄為止，將其與樞軸記錄互相交換。(3)重復(fù)(1)(2)直至i=j為止。完成一趟排序，完成一次分割(以K為分界線)，對前后兩個子表按上述原則再分割，直到所有子表的表長不超過1(為空)為止。1.6.3交換排序編輯ppt27391176966650494939669676112750i第1次交換(向前,小的與樞軸交換)即27與49交換.第2次交換:(向后,大的與樞軸交換)即66與49換,27396696761150i49jj第3次交換:11與49換2739119676665049ji2739967611665049ji完成一趟排序:初始關(guān)鍵字第4次換:96與49換ijj2739114976966650舉例:將（49，39，66，96，76,11，27，50）進行一趟快速排序

分析:(取第一個數(shù)49為樞軸,即K=49,空處是樞軸為49)編輯ppt4939669676112750[273911]49[76966650]一次劃分之后快速排序的全過程初始關(guān)鍵字分別進行快速排序[11]27[39]5066結(jié)束結(jié)束結(jié)束[5066]76[96]結(jié)束1127394950667696有序序列時效分析:平均時間復(fù)雜度最佳為O(nlog2n)。最壞情況時間效率為O(n2)。編輯ppt基本思想：

每次從待排序的記錄中選出關(guān)鍵字最小的記錄，順序存放在已排序的記錄序列的后面，直到全部排完。選擇排序種類:

直接選擇排序和堆排序1.直接選擇排序(以升序為例)首先從所有n個待排序記錄中選擇關(guān)鍵字最小的記錄，與第1個記錄交換(第1遍進行n-1次比較)。再從剩下的n-1個記錄中選出關(guān)鍵字最小的記錄，與第2個記錄交換(第2遍進行n-2次比較)。重復(fù)操作進行n-1遍，直到待排序序列全部有序為止。1.6.4選擇排序編輯ppt1.直接選擇排序

正序：移動次數(shù)為0逆序：移動次數(shù)為3(n-1)執(zhí)行n(n-1)/2次比較舉例:將（89，21，56，48，85，16，19，47）直接選擇排序原序列8921564885161947i=1162156488589

1947i=21619564885892147i=316192148858956

47

i=41619214785895648

i=516192146488956

85

i=6161921464856

89

85

i=716192146485685

89

最后結(jié)果進行n-1=7次選擇1.6.4選擇排序

時效分析:編輯ppt選擇法排序for(i=0;i<N-1;i++){

k=i;

for(j=i+1;j<N;j++)

if(a[j]>a[k])k=j;

if(k!=i){temp=a[i];a[i]=a[k];a[k]=temp;}}編輯ppt例初始：[49386597761327]kji=11349一趟：

13

[386597764927]i=22738二趟：

1327

[6597764938]三趟：

132738

[97764965]四趟：

13273849

[769765]五趟：

1327384965

[9776]六趟：

132738496576

[97]kkkkjjjjjjjjjj從小到大排序編輯ppt2.堆排序堆定義：n個元素的序列{K1，K2，…，Kn}，當(dāng)且僅當(dāng)滿足下列關(guān)系時，稱為堆。

ki≤k2i

ki≤k2i+1

ki≥k2iki≥k2i+1

小根堆或大根堆堆結(jié)構(gòu)(完全二叉樹表示)：將序列對應(yīng)的一維數(shù)組看成一個完全二叉樹。在堆中,堆頂元素必為序列中n個元素的最小值(或最大值)。

小根堆251556103070255630701510

大根堆其中:（i=1，2，…，n/2）1.6.4選擇排序編輯ppt首先包括n個元素的序列建堆,輸出堆頂最小值。得到n個元素中最小元素。然后再對剩下n-1個元素重建堆,輸出堆頂元素。得到n個元素中次小元素。反復(fù)執(zhí)行(直到剩下子序列為空)，便得到一個有序列。2.堆排序排序過程:

兩個問題:實現(xiàn)堆排序需解決

(1)如何將n個元素的無序序列建成一個堆。(2)輸出堆頂元素后，調(diào)整剩余元素成為一個新堆。

輸出堆頂元素后，以堆中最后一個元素代替之。此時根結(jié)點左、右子樹均為堆，僅需自上而下調(diào)整即可。1.6.4選擇排序方法：將根結(jié)點與左、右子樹根結(jié)點比較，若不滿足堆條件，則較小值與根結(jié)點交換。順序：從完全二叉樹最后一個非終端結(jié)點(第n/2個元素)開始，直到根結(jié)點(第一個元素)為止，對每一個結(jié)點，調(diào)整建堆。編輯ppt舉例:一個無序序列(49,39,66,96,76,11,27,50)建小根堆的過程1.從第一個非葉子結(jié)點(序號=n/2=8/2=4,即圖中值為96的結(jié)點開始篩選,篩選原則是保證父結(jié)點的值要小于或等于葉子接點4939966676112750無序序列4939506676112796第4個結(jié)點96被篩選后狀態(tài)4939501176662796第3個結(jié)點66被篩選后狀態(tài)

4939501176662796第2個結(jié)點39被篩選后狀態(tài)編輯ppt

目前的堆中,堆頂元素11為最小值,輸出后,重新對n-1個元素重新建一個新堆,新堆中的堆頂是剩余的n-1個元素中的最小值,n個元素中的次最小值.113950497666279649被篩選后建成的堆11395027766649964939501176662796第2個結(jié)點篩選完畢該處理第1個結(jié)點編輯ppt舉例:輸出堆頂元素并建新堆過程堆113950277666499611與96交換后情形輸出堆頂元素之后,以堆中最后一個元素替代之,此時根結(jié)點的左、右子樹均為堆,僅需自上至下進行調(diào)整即可。1139502776664996113950967666492727與96交換后情形1139504976669627

調(diào)整后新堆,27為新堆中的最小值編輯ppt27395049766696輸出27,用96替代

11112796504976663996與39換509649766639112796與50換39504976669627

調(diào)整后新堆,27為新堆中的最小值11調(diào)整后新堆,39為新堆中的最小值編輯ppt繼續(xù)此過程

調(diào)整后新堆,39為新堆中的最小值50964976663911273950964976661127輸出堆頂元素（堆頂元素和樹中最后一個結(jié)點對調(diào)）重建堆（因為除了堆頂?shù)母Y(jié)點，左右子樹已經(jīng)是堆，自上而下進行調(diào)整即可）反復(fù)執(zhí)行直到剩下子序列為空（便得到一個有序列）堆排序的時效分析:

最壞情況下，時間復(fù)雜度為O(nlog2n)。僅需一個記錄大小供交換用的輔助存儲空間，適合規(guī)模較大的線性表。編輯ppt插入排序交換排序選擇排序直接插入排序希爾排序冒泡排序快速排序直接選擇排序堆排序適用于n較小情況,或表中每個元素與其最終位置不遠,記錄本身信息量較大時若適用于數(shù)據(jù)元素初始狀態(tài)基本有序適用于n較大情況,是目前基于內(nèi)部排序的方法中最好的適用于n較小情況,且記錄本身信息量較大時適用于n較大情況,最壞情況下,比較次數(shù)n(n-1)/2最壞情況下,時間復(fù)雜度是O(n1..5)最壞情況下,比較次數(shù)n(n-1)/2最壞情況下,比較次數(shù)n(n-1)/2最壞情況下,比較次數(shù)n(n-1)/2最壞情況下,比較次數(shù)nlog2n排序小結(jié)編輯ppt查找與排序補充習(xí)題講解1.鏈表適用于_____查找.A.順序B.二分法C.順序,也能二分法D.隨機2.對長度為n的線性表進行順序查找,在最壞情況下所需要的比較次數(shù)為____.A.log2nB.n/2C.nD.n+1（05年4月）3.已知一個有序表為(13、18、24、35、47、50、62、83、90、115、134），當(dāng)使用二分法查找90的元素時，查找成功的比較次數(shù)為____