計算機軟件基礎課件：排序

排序BasicsofComputerSoftware答辯人：XXX排序的概念內(nèi)排序外排序1排序?qū)⒁粋€數(shù)據(jù)元素的任意序列，重新排列成一個按關鍵字有序的序列2內(nèi)排序在排序期間數(shù)據(jù)對象全部存放在內(nèi)存的排序3外排序在排序期間全部對象個數(shù)太多，不能同時存放在內(nèi)存，必須根據(jù)排序過程的要求，不斷在內(nèi)、外存之間移動的排序排序的基本概念排序的基本概念排序的時間開銷02排序的穩(wěn)定性01如果在對象序列中有兩個對象r[i]和r[j],它們的排序碼k[i]==k[j]，在排序之前,對象r[i]排在r[j]前面。如果在排序之后,對象r[i]仍在對象r[j]的前面,則稱這個排序方法是穩(wěn)定的,否則稱這個排序方法是不穩(wěn)定的排序的時間開銷是衡量算法好壞的最重要的標志。排序的時間開銷一般可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動次數(shù)來衡量。目錄起泡排序1插入排序2選擇排序3快速排序45希爾排序6歸并排序7基數(shù)排序8堆排序起泡排序PART1基本方法：設待排序?qū)ο笮蛄兄械膶ο髠€數(shù)為n。一般地，第i趟起泡排序從1到n-i+1依次比較相鄰兩個記錄的關鍵字，如果發(fā)現(xiàn)逆序，則交換之，其結(jié)果是這n-i+1個記錄中，關鍵字最大的記錄被交換到第n-i+1的位置上，最多作n-1趟。排序算法：起泡排序252149251682125251684921251682549211682525492125254916825214925168原始關鍵字第一趟排序第二趟排序第三趟排序第四趟排序第五趟排序voidBubbleSort(intV[],intn){inti=1;intexchange=1;while(i<n&&exchange){exchange=0; //標志置為0,假定未交換

for(intj=0;j<=n-1-i;j++)if(V[j]>V[j+1]){//逆序Swap(V[j],V[j+1]);//交換

exchange=1;//標志置為1,有交換

}i++;}}起泡排序的算法起泡排序分析1每趟排序，對象均向最終位置移動第i趟對序列V[0],…,V[n-i]進行排序，將最大的對象交換到V[n-i]的位置，其它對象也都向排序的最終位置移動2最多趟數(shù)最多做n-1趟起泡就能把所有對象排好序.3最少趟數(shù)在序列已經(jīng)按從小到大排好序時，只執(zhí)行一趟起泡排序，做n-1次排序碼比較，不移動對象。這是最快的情形4最壞情形最壞的情形是算法執(zhí)行n-1趟起泡，第i趟做n-i次排序碼比較，執(zhí)行n-i次對象交換。此時，共進行n(n-1)/2次比較和交換，起泡排序是一個穩(wěn)定的排序方法。插入排序PART2具體來說：當插入第I(I

1)個對象時,前面的V[0],V[1],…,V[i-1]已經(jīng)排好序。這時,用V[i]的排序碼與V[i-1],V[i-2],…的排序碼順序進行比較,找到插入位置即將V[i]插入,原來位置上的對象向后順移。具體來說02基本思想01每步將一個待排序的對象,按其排序碼大小,插入到前面已經(jīng)排好序的一組對象的適當位置上,直到對象全部插入為止。當插入第i個對象時，前面的V[0],V[1],…,V[i-1]已經(jīng)排好序。這時，用V[i]的排序碼與V[i-1],V[i-2],…的排序碼順序進行比較，找到插入位置即將V[i]插入，

原來位置上的對象向后順移。排序算法：插入排序2516252149251682125492516821254916821252549825214925168原始關鍵字第一趟排序第二趟排序第三趟排序第四趟排序第五趟排序821252549162516temp排序算法：插入排序過程typedefintSortData;voidInsertSort(SortDataV[],intn){

SortDatatemp;inti,j;for(i=1;i<n;i++){temp=V[i];for(j=i;j>0;j--)//從后向前順序比較

if(temp<V[j-1])V[j]=V[j-1];elsebreak;V[j]=temp;}}排序算法：插入排序算法插入排序算法分析1設待排序?qū)ο髠€數(shù)為n,則該算法的主程序執(zhí)行n-1趟2排序碼比較次數(shù)和對象移動次數(shù)與對象排序碼的初始排列有關3最好情況下,排序前對象已按從小到大有序,每趟只需與前面有序序列的最后一個對象比較1次,移動2次對象,總的排序碼比較次數(shù)為n-1,對象移動次數(shù)為2(n-1)4最壞情況下,第i趟時第i個對象必須與前面i個對象都做比較,并且每做1次比較就要做1次數(shù)據(jù)移動5直接插入排序是一種穩(wěn)定的排序方法選擇排序PART3將待排序數(shù)組分為有序和無序兩組（初始情況下有序組為空，無序組是所有待排記錄），每一趟（設第i趟）都從無序組中選擇出排序碼最小的記錄,作為有序序列中的第i個記錄。待到第n-1趟作完,待排序記錄只剩下1個,就不用再選了。排序算法：選擇排序基本思想直接選擇排序的步驟1在一組對象V[i]～V[n-1]中選擇具有最小排序碼的對象2若它不是這組對象中的第一個對象,則將它與這組對象中的第一個對象對調(diào)在這組對象中剔除這個具有最小排序碼的對象。在剩下的對象V[i+1]～V[n-1]中重復執(zhí)行第1、2步,直到剩余對象只有一個為止325214925168ij25214925168kij25214925168兩種選擇排序的區(qū)別原始關鍵字一般選擇排序直接選擇排序2549252149251688214925162581649212581621252525214925168原始關鍵字第一趟排序第二趟排序第三趟排序第四趟排序第五趟排序25162125498kkkkkiiiiijjjjj直接選擇排序的過程typedefintSortData;voidSelectSort(SortDataV[],intn){for(inti=0;i<n-1;i++){intk=i;//選擇具有最小排序碼的對象

for(intj=i+1;j<n;j++)if(V[j]<V[k])k=j;//當前具最小排序碼的對象

if(k!=i)//對換到第i個位置

Swap(V[i],V[k]);} }直接選擇排序算法直接選擇排序算法分析1比較次數(shù)與對象的初始排列無關。有n個對象的序列,則第i趟排序的比較次數(shù)總是n-i次?？偟呐判虼a比較次數(shù)為：2對象的交換次數(shù)與對象序列的初始排列有關。當序列的初始狀態(tài)是按其排序碼從小到大有序時，,對象的交換次數(shù)為0，移動次數(shù)RMN=0，達到最少3最壞情況是每一趟都要進行交換，總的對象移動次數(shù)為RMN=3(n-1)4直接選擇排序是一種不穩(wěn)定的排序方法

快速排序PART4基本思想排序算法：快速排序任取序列中某個對象作為基準,將整個對象序列劃分為左右兩個子序列：

左側(cè)子序列中所有對象都小于等于基準對象右側(cè)子序列中所有對象都大于基準對象基準對象排在這兩個子序列中間（這也是該對象最終應安放的位置）。分別對這兩個子序列重復上述方法，直到所有的對象都排在相應位置上為止?；鶞蕦ο笠卜Q為樞軸（或支點）記錄。2521492516882116252549排序算法：快速排序25214925168567834854536hl918480lh快速排序的分隔算法intPartition(SqListA[],intlow,inthigh){X=A[low];//子表的第一個記錄作基準對象

While(low<high){While(low<high&&A[high]>=X)--high;A[low]=A[high];//小于基準對象的移到區(qū)間的左側(cè)

While(low<high&&A[low]<=X)++low;A[high]=A[low];//大于基準對象的移到區(qū)間的右側(cè)

}A[low]=X;returnlow;}快速排序的分隔算法voidQuickSort(SqList&A,intlow,inthigh){//在序列l(wèi)owhigh中遞歸地進行快速排序

if(low<high){ intloc=Partition(A,low,high);//分割

QuickSort(A,low,loc-1);//對左序列同樣處理

QuickSort(A,loc+1,high);//對右序列同樣處理

}}快速排序算法快速排序算法分析1算法partition利用序列第一個對象作為基準，將整個序列劃分為左右兩個子序列。只要是小于基準對象都移到序列左側(cè),最后基準對象安放到位,返回其位置2快速排序是遞歸的，需要有一個棧存放每層遞歸調(diào)用時的指針和參數(shù)3可以證明,函數(shù)quicksort的平均計算時間也是O(nlog2n)。實驗結(jié)果表明:就平均計算時間而言,快速排序是所有內(nèi)排序方法中最好的一個。4快速排序是一種不穩(wěn)定的排序方法快速排序算法分析5快速排序的趟數(shù)取決于原始數(shù)據(jù)的排列方式。6如果每次劃分對一個對象定位后,該對象的左側(cè)子序列與右側(cè)子序列的長度相同,則下一步將是對兩個長度減半的子序列進行排序,這是最理想的在最壞的情況,即待排序?qū)ο笮蛄幸呀?jīng)按其排序碼從小到大排好序,或是一個逆序序列的情況下,每次劃分只得到一個比上一次少一個對象的子序列?？偟呐判虼a比較次數(shù)將達7希爾排序PART5主講人：希爾排序是插入排序的一種，又稱縮小增量排序，為解決插入排序每次只能將數(shù)據(jù)移動一位，在數(shù)組較大且基本無序的情況下性能出現(xiàn)的惡化，所以引入希爾算法。排序算法：希爾排序問題提出先取一個小于n的步長d1把表中全部記錄分成d1個組，所有距離為d1的倍數(shù)的記錄放在同一個組中，在各組中進行直接插入排序。然后取第二個步長d2<d1,重復上述過程，直到所取到的di=1,即所有記錄已放在同一組中，再進行直接插入排序。由于此時已經(jīng)具有較好的局部有序性，故可以很快得到最終結(jié)果。但到目前為止，尚未求得一個最好的增量序列，希爾提出的方法是d1=?n/2?，di+1=?di/2?

,并且最后一個增量等于1。排序算法：希爾排序算法思想406549132750763827134938655013273850657697769797493865977613原始關鍵字第一趟排序5027d=4d=2第二趟排序d=1第三趟排序排序算法：希爾排序voidShellSort(ElemTypeA[],intn){for(d=n/2;d>=1;d=d/2)//步長變化

for(i=d+1;i<=n;++i)if(A[i]<A[i-d])//需將A[i]插入有序增量子表{

A[0]=A[i];for(j=i-d;j>0&&A[0]<A[j];j=j-d)A[j+d]=A[j];//記錄后移，查找插入位置

A[j+d]=A[0];//插入}//if}希爾排序算法排序的時間復雜度02排序的穩(wěn)定性01當相同關鍵字的記錄被劃分到不同的子表時，可能會改變它們之間的相對次序，因此，希爾排序是一種不穩(wěn)定的排序方法。O(n*log2n)希爾排序算法分析歸并排序PART6歸并排序有兩種實現(xiàn)方法：自頂向下和自底向上。1.自頂向下的方法?

采用分治法進行自頂向下的算法設計，形式更為簡潔，用遞歸，效率不如自底向上2.自底向上的方法?基本思想是：第1趟歸并排序時，將待排序的數(shù)列A[1..n]看作是n個長度為1的有序子序列，將這些子序列兩兩歸并形成?n/2?個有序子序列第2趟歸并則是將第1趟歸并所得到的?n/2?個有序的子序列兩兩歸并，如此反復，直到最后得到一個長度為n的有序序列為止。

上述的每次歸并操作，均是將兩個有序的子序列合并成一個有序的子序列，故稱其為"二路歸并排序"。排序算法：歸并排序493865977613原始關鍵字5027第一趟排序38496597137650273849659713277650第二趟排序1327384950659776第三趟排序排序算法：歸并排序歸并排序算法分析排序的時間復雜度02排序的穩(wěn)定性01歸并排序中歸并的算法并不會將相同關鍵字的元素改變相對次序，所以歸并排序是穩(wěn)定的。O(n*log2n)基數(shù)排序PART7比如，撲克牌的花色基數(shù)為4，面值基數(shù)為13。在整理撲克牌時，既可以先按花色整理，也可以先按面值整理。按花色整理時，先按?、?、?、?的順序分成4摞（分配），再按此順序再疊放在一起（收集），然后按面值的順序分成13摞（分配），再按此順序疊放在一起（收集），如此進行二次分配和收集即可將撲克牌排列有序。如果反過來，先按面值整理，再按花色整理，也能將撲克牌排列有序，但和上面的排序結(jié)果是不一樣的排序算法：基數(shù)排序多關鍵碼排序按照從最主位關鍵碼到最次位關鍵碼或從最次位到最主位關鍵碼的順序逐次排序，分兩種方法：最高位優(yōu)先法，簡稱MSD法和最低位優(yōu)先，簡稱LSD法，我們現(xiàn)在看LSD法在數(shù)值排序中的應用對數(shù)字型或字符型的單關鍵字，可以看作由多個數(shù)位或多個字符構(gòu)成的多關鍵字，此時可以采"分配-收集”的方法進行排序，這一過程稱作基數(shù)排序法，其中每個數(shù)字或字符可能的取值個數(shù)稱為基數(shù)。在“分配-收集”的過程中，為保證排序的穩(wěn)定性，分配過程中裝箱及收集過程中的連接必須按先進先出原則進行。排序算法：基數(shù)排序557322934314原始數(shù)據(jù)第一趟7665398165289727012345678965813914654328932276972773554381227393142765657697552839012345678965813914654328932276972773553914222728438165657376559397第二趟排序算法：基數(shù)排序前面說的幾大排序算法，大部分時間復雜度都是O(n2)，也有部分排序算法時間復雜度是O(nlog2n)。而基數(shù)排序卻能實現(xiàn)O(n)的時間復雜度。但基數(shù)排序的缺點是：首先是空間復雜度比較高，需要的額外開銷大。排序有兩個數(shù)組的空間開銷，一個存放待排序數(shù)組，一個就是所謂的桶。初看起來，基數(shù)排序的執(zhí)行效率似乎好的讓人無法相信，所有要做的只是把原始數(shù)據(jù)項從數(shù)組復制到桶，然后再復制回去。如果有n個數(shù)據(jù)項，數(shù)據(jù)位數(shù)最多是d位，則有n*d次復制，復制的次數(shù)與數(shù)據(jù)項的個數(shù)成正比，即O(n)。這是我們看到的效率最高的排序算法。不幸的是，數(shù)據(jù)項越多，就需要更長的關鍵字，如果數(shù)據(jù)項增加10倍，那么關鍵字必須增加一位（多一輪排序）。復制的次數(shù)和數(shù)據(jù)項的個數(shù)與關鍵字長度成正比，可以認為關鍵字長度是N的對數(shù)。因此在大多數(shù)情況下，基數(shù)排序的執(zhí)行效率倒退為O(N*logN)，和快速排序差不多。基數(shù)排序的算法分析堆排序PART8堆是一棵順序存儲的完全二叉樹。其中：小頂堆：每個結(jié)點的關鍵字都不大于其孩子結(jié)點的關鍵字

大頂堆：每個結(jié)點的關鍵字都不小于其孩子結(jié)點的關鍵字排序算法：基數(shù)排序121191610732845堆排序的過程1首先將序列構(gòu)建成為大頂堆這樣滿足了大頂堆那條性質(zhì)：位于根節(jié)點的元素一定是當前序列的最大值2取出當前大頂堆的根節(jié)點，將其與序列末尾元素進行交換此時：序列末尾的元素為已排序的最大值；但位于根節(jié)點的值并不一定滿足堆的性質(zhì)3對交換后的n-1個序列元素進行調(diào)整，使其滿足大頂堆的性質(zhì)將剩余序列重新調(diào)整成堆4重復2-3步，直至堆中只有1個元素為止實現(xiàn)序列排序1234567891011121314732293435514286539816576972712345678910111213147322934355142865398165769727堆排序演示：堆的建立1234567891011121314978193656576284339552273142712345678910111213149781936565762843395522731427第1趟堆排序演示：第1趟1234567891011121314938176656573284339552227149712345678910111213149381766565732843395522271497第2趟堆排序演示：第2趟1234567891011121314816576436573281439552227939712345678910111213148165764365732814395522279397第3趟堆排序演示：第3趟1234567891011121314766573436527281439552281939712345678910111213147665734365272814395522819397第4趟堆排序演示：第1趟1234567891011121314736528436527221439557681939712345678910111213147365284365272214395576819397第5趟堆排序演示：第5趟1234567891011121314656528435527221439737681939712345678910111213146565284355272214397376819397第6趟堆排序演示：第6趟1234567891011121314655528433927221465737681939712345678910111213146555284339272214657376819397第7趟堆排序演示：第7趟1234567891011121314554328143927226565737681939712345678910111213145543281439272265657376819397第8趟堆排序演示：第8趟1234567891011121314433928142227556565737681939712345678910111213144339281422275565657376819397第9趟堆排序演示：第9趟1234567891011121314392728142243556565737681939712345678910111213143927281422435565657376819397第10趟堆排序演示：第10趟1234567891011121314282722143943556565737681939712345678910111213142827221439435565657376819397第11趟堆排序演示：第11趟1234567891011121314271422283943556565737681939712345678910111213142714222839