第7章-排序-Sorting第3章課件

第7章排序Sorting[嚴陳]第3章第7章排序Sorting1內容提要排序的基本概念排序算法的分析插入排序(直接,二分)交換排序(冒泡,快速)選擇(selection,堆排序)歸并(merge)基數排序內容提要排序的基本概念2基本概念排序：將一組雜亂無章的數據按一定的規(guī)律順次排列起來。數據表(datalist):它是待排序數據對象的有限集合。排序碼(key):通常數據對象有多個屬性域,即多個數據成員組成,其中有一個屬性域可用來區(qū)分對象,作為排序依據。該域即為排序碼。每個數據表用哪個屬性域作為排序碼，要視具體的應用需要而定。基本概念排序：將一組雜亂無章的數據按一定的規(guī)律順次排列起來。3分類內排序與外排序內排序是指在排序期間數據對象全部存放在內存的排序；外排序是指在排序期間全部對象個數太多，不能同時存放在內存，必須根據排序過程的要求，不斷在內、外存之間移動的排序。分類內排序與外排序4排序算法的穩(wěn)定性如果在對象序列中有兩個對象r[i]和r[j],它們的排序碼k[i]==k[j],

穩(wěn)定的:排序前后,對象r[i]和r[j]的相對位置不變

不穩(wěn)定:else排序算法的穩(wěn)定性如果在對象序列中有兩個對象r[i]和r[j]5算法評價時間開銷:排序的時間開銷可用算法執(zhí)行中的數據比較次數與數據移動次數來衡量。算法運行時間代價的大略估算一般都按平均情況進行估算。對于那些受對象排序碼序列初始排列及對象個數影響較大的，需要按最好情況和最壞情況進行估算空間開銷：算法執(zhí)行時所需的附加存儲算法評價時間開銷:6插入排序插入排序7第7章-排序-Sorting第3章課件8第7章-排序-Sorting第3章課件9直接插入排序直接插入排序10直接插入排序直接插入排序11直接插入排序:算法分析設待排序對象個數為n,則該算法的主程序執(zhí)行n-1趟排序碼比較次數和對象移動次數與對象排序碼的初始排列有關最好情況下,排序前對象有序 比較(KCN):n-1;移動次數(RMN):為2(n-1)最壞情況下,第i趟時第i個對象必須與前面i個對象都做排序碼比較,并且每做1次比較就要做1次數據移動。

直接插入排序:算法分析設待排序對象個數為n,則該算法的主程序12在平均情況下的排序碼比較次數和對象移動次數約為n2/4。因此，直接插入排序的時間復雜度為o(n2)

直接插入排序是一種穩(wěn)定的排序方法在平均情況下的排序碼比較次數和對象移動次數約為n2/4。因此13二分插入排序(BinaryInsertsort)

基本思想是:設在順序表中有一個對象序列V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,V[i-1]是已經排好序的對象。在插入V[i]時,利用二分搜索法尋找V[i]的插入位置。二分插入排序(BinaryInsertsort)基本思14二分插入排序二分插入排序15二分插入排序:分析二分搜索比順序搜索查找快,所以二分插入排序就平均性能來說比直接插入排序要快。它所需的排序碼比較次數與待排序對象序列的初始排列無關,僅依賴于對象個數。在插入第i個對象時,需要經過log2i+1次排序碼比較,才能確定它應插入的位置。因此,將n個對象(為推導方便,設為n=2k)用折半插入排序所進行的排序碼比較次數為二分插入排序是一個穩(wěn)定的排序方法。二分插入排序:分析二分搜索比順序搜索查找快,所以二分插入排序16當n較大時,總排序碼比較次數比直接插入排序的最壞情況要好得多,但比其最好情況要差。在對象的初始排列已經按排序碼排好序或接近有序時,直接插入排序比折半插入排序執(zhí)行的排序碼比較次數要少。折半插入排序的對象移動次數與直接插入排序相同,依賴于對象的初始排列當n較大時,總排序碼比較次數比直接插入排序的最壞情況要好得17使用鏈表插入排序每插入一個對象，最大排序碼比較次數等于鏈表中已排好序的對象個數最小排序碼比較次數為1

故總的排序碼比較次數最小為(n-1)最大為移動次數為0空間增加了指針域,和頭結點使用鏈表插入排序每插入一個對象，最大排序碼比較次數等于鏈表18交換排序交換排序19交換排序數據兩兩比較，逆序交換，直到全部有序冒泡，快速交換排序數據兩兩比較，逆序交換，直到全部有序20冒泡排序(BubbleSort)對象個數n。最多作最多作n-1趟，i=1,2,…,n-1i趟中從后向前j=n-1,n-2,……,i，順次兩兩比較比較如果發(fā)生逆序，則 交換V[j-1]和V[j]。冒泡排序(BubbleSort)對象個數n。最多作最多作21VoidBubbleSort(int*data,intn){ i=0;while(i<n-1){ last=n-1; for(j=n-1;j>i;j--) If(data[j]<data[j-1]){交換數據；last=j;}i=last; }}i是無序集的下界VoidBubbleSort(int*data,i22算法分析最好:n-1次比較,移動為0最壞需要一個附加空間穩(wěn)定算法分析最好:n-1次比較,移動為023快速排序基本思想：任選一個記錄，以其關鍵字為“樞軸”，序列中比它小的移動到該記錄之前，反之移動到它之后通過一趟排序將待排的記錄分割成兩個區(qū)域，一個區(qū)域中記錄的關鍵字比另一個區(qū)域的關鍵字?。ㄒ淮蝿澐郑┤缓笞笥覂蛇叿謩e處理直到排好快速排序基本思想：24快速排序劃分:pivotpos=low;pivot=D[low];for(i=low+1;i<=high;i++) if(D[i].Key<=pivot.Key&&++pivotpos!=i) D[pivotpos]和D[i]交換;D[pivotpos]和D[low]交換;快速排序劃分:25第7章-排序-Sorting第3章課件26第7章-排序-Sorting第3章課件27快速排序算法分析N個元素,排列有n!種,每個元素可以充當界點,界點的情況有n種平均時間復雜性:T(n)=cn+∑[T(k-1)+T(n-k)]/n,k=1:n設:T(0)=T(1)=b;T(n)=cn+2∑T(i)/n,i=0:n-1nT(n)=c(2n-1)+(n+1)T(n-1)T(n)<=2c(n+1)log(n+1)+b(n+1)/2快速排序算法分析N個元素,排列有n!種,每個元素可以充當界點28快速排序算法分析平均情況下,時間漸進復雜度是O(nlogn)，通常認為是在平均情況下的最佳排序.最壞情況:正序比較次數T(n)=(n-1)+(n-2)+…+1=n2/2,可以通過隨機選擇界點來避免將遞歸改為非遞歸快速排序算法分析平均情況下,時間漸進復雜度是O(nlogn)29快速排序算法分析空間最壞情況需要的棧O(n)可以通過先處理短的分段,來降低輔助空間到O(logn),當只有1個元素的時候不需要保存上下界,而非均勻分段時,下降的速度更快.不穩(wěn)定對于n較大的平均情況而言,快速排序是“快速”的,但是當n很小時,這種排序方法往往比其它簡單排序方法還要慢?？焖倥判蛩惴ǚ治隹臻g最壞情況需要的棧O(n)30上機練習:P171:插入排序P221:快速排序上機練習:P171:插入排序31第7章排序(2)第7章排序(2)32回顧排序的基本概念排序算法的分析插入排序(直接,二分)交換排序(冒泡,快速)回顧排序的基本概念33第7章-排序-Sorting第3章課件34內容提要插入排序(直接,二分)交換(冒泡,快速)選擇(selection,堆排序)歸并(merge)基數排序內容提要插入排序(直接,二分)35選擇排序N個元素,每次挑出最大或者最小,執(zhí)行(n-1)次循環(huán)選擇排序N個元素,每次挑出最大或者最小,執(zhí)行(n-1)次循環(huán)36第7章-排序-Sorting第3章課件37直接選擇排序的排序碼比較次數KCN與整個待排序對象序列象的初始排列無關。移動次數:最好:0最壞:3(n-1)穩(wěn)定直接選擇排序的排序碼比較次數KCN與整個待排序對象序列象的38堆排序樹性選擇排序堆的定義：n個元素的序列{k0，k1，……，kn-1}，當且僅當滿足以下關系時，稱之為堆最小化堆ki<=k2i+1ki<=k2i+2最大化堆Ki>=k2i+1ki>=k2i+2(i=0,1,2,……,(n-2)/2)最大化堆最大的結點一定出現在堆頂上。堆排序樹性選擇排序39歸并排序歸并，是將兩個或兩個以上的有序表合并成一個新的有序表。對象序列initList中兩個有序表V[1]…V[m]和V[m+1]…V[n]。它們可歸并成一個有序表,存于另一對象序列mergedList的V[1]…V[n]中。這種歸并方法稱為兩路歸并(2-waymerging)

歸并排序歸并，是將兩個或兩個以上的有序表合并成一個新的有序表40設變量i和j分別是表V[1]…V[m]和V[m+1]…V[n]的當前檢測指針。變量k是存放指針。設變量i和j分別是表V[1]…V[m]和V[m+1]41迭代的歸并排序算法

迭代的歸并排序算法就是利用兩路歸并過程進行排序的。其基本思想是：假設初始序列有n個對象，首先把它看n個長度為1的有序子序列,兩兩并歸,重復上述操作,直到得到一個序列.迭代的歸并排序算法

迭代的歸并排序算法就是利用兩路歸并過程進42算法分析輔助空間占用多穩(wěn)定算法分析輔助空間占用多43遞歸的表歸并排序

與快速排序類似，歸并排序也可以利用劃分為子序列的方法遞歸實現。在遞歸的歸并排序方法中，首先要把整個待排序序列劃分為兩個長度大致相等的部分,左子表和右子表。對子表分別遞歸地進行排序,然后再把排好序的兩個子表并歸.遞歸的表歸并排序

與快速排序類似，歸并排序也可以利用劃分為子44算法分析鏈表的歸并排序方法的遞歸深度為O(log2n)，對象排序碼的比較次數為O(nlog2n)。穩(wěn)定算法分析鏈表的歸并排序方法的遞歸深度為O(log2n)，對45基數排序不進行關鍵字的比較,而是利用”分配”和”收集”收集后的序列：2、52、5、7、17、18、9基數排序不進行關鍵字的比較,而是利用”分配”和”收集”46第7章-排序-Sorting第3章課件47空間：采用順序分配，顯然不合適。由于每個口袋都有可能存放所有的待排序的整數。所以，額外空間的需求為10n，太大了。采用鏈接分配是合理的。額外空間的需求為n，通常再增加指向每個口袋的首尾指針就可以了。在一般情況下，設每個鍵字的取值范圍為d,首尾指針共計2×radix個，總的空間為O(n+2×radix)。時間：上例中每個數計有2位，因此執(zhí)行2次分配和收集就可以了。在一般情況下，每個結點有d位關鍵字，必須執(zhí)行d次分配和收集操作。 每次分配的代價：O(n) 每次收集的代價：O(radix) 總的代價為：O(d×(n+radix))空間：采用順序分配，顯然不合適。由于每個口袋都有可能存放所有48第7章-排序-Sorting第3章課件49voidRadixSort(staticlinklistlist,intd,intradix) {intrear[radix],front[radix]; for(i=0;i<list.Size;i++) list.Vector[i].link=i+1; list.Vector[CurrentSize].link=0; intcurrent=1;//最前面的結點下標為1,0號結點用作頭結點 for(i=d-1;i>=0;i--){ for(intj=0;j<radix;j++)front[j]=0; while(current!=0) {intk=list.Vector[current].key[i]; if(front[k]==0)front[k]=current; elselist.Vextor[rear[k]].link=current; rear[k]=current; current=list.Vector[current].link;} j=0; while(front[j]==0)j++; list.Vector[0].link=current=front[j]; intlast=rear[j]; for(k=j+1;k<radix;k++) if(front[k]){list.Vector[last].link=front[k];last=rear[k];} list.Vector[last].link=0; }}//本程序并不十分嚴格，請大家作為算法來看。voidRadixSort(staticlinklistl50O(nlogn)O(n2)O(n)(基數排序)O(nlogn)O(n2)O(n)(基數排序)51排序算法選擇待排序的個數記錄本身的大小關鍵字的分布排序穩(wěn)定性的要求排序算法選擇待排序的個數52第7章排序Sorting[嚴陳]第3章第7章排序Sorting53內容提要排序的基本概念排序算法的分析插入排序(直接,二分)交換排序(冒泡,快速)選擇(selection,堆排序)歸并(merge)基數排序內容提要排序的基本概念54基本概念排序：將一組雜亂無章的數據按一定的規(guī)律順次排列起來。數據表(datalist):它是待排序數據對象的有限集合。排序碼(key):通常數據對象有多個屬性域,即多個數據成員組成,其中有一個屬性域可用來區(qū)分對象,作為排序依據。該域即為排序碼。每個數據表用哪個屬性域作為排序碼，要視具體的應用需要而定?；靖拍钆判颍簩⒁唤M雜亂無章的數據按一定的規(guī)律順次排列起來。55分類內排序與外排序內排序是指在排序期間數據對象全部存放在內存的排序；外排序是指在排序期間全部對象個數太多，不能同時存放在內存，必須根據排序過程的要求，不斷在內、外存之間移動的排序。分類內排序與外排序56排序算法的穩(wěn)定性如果在對象序列中有兩個對象r[i]和r[j],它們的排序碼k[i]==k[j],

穩(wěn)定的:排序前后,對象r[i]和r[j]的相對位置不變

不穩(wěn)定:else排序算法的穩(wěn)定性如果在對象序列中有兩個對象r[i]和r[j]57算法評價時間開銷:排序的時間開銷可用算法執(zhí)行中的數據比較次數與數據移動次數來衡量。算法運行時間代價的大略估算一般都按平均情況進行估算。對于那些受對象排序碼序列初始排列及對象個數影響較大的，需要按最好情況和最壞情況進行估算空間開銷：算法執(zhí)行時所需的附加存儲算法評價時間開銷:58插入排序插入排序59第7章-排序-Sorting第3章課件60第7章-排序-Sorting第3章課件61直接插入排序直接插入排序62直接插入排序直接插入排序63直接插入排序:算法分析設待排序對象個數為n,則該算法的主程序執(zhí)行n-1趟排序碼比較次數和對象移動次數與對象排序碼的初始排列有關最好情況下,排序前對象有序 比較(KCN):n-1;移動次數(RMN):為2(n-1)最壞情況下,第i趟時第i個對象必須與前面i個對象都做排序碼比較,并且每做1次比較就要做1次數據移動。

直接插入排序:算法分析設待排序對象個數為n,則該算法的主程序64在平均情況下的排序碼比較次數和對象移動次數約為n2/4。因此，直接插入排序的時間復雜度為o(n2)

直接插入排序是一種穩(wěn)定的排序方法在平均情況下的排序碼比較次數和對象移動次數約為n2/4。因此65二分插入排序(BinaryInsertsort)

基本思想是:設在順序表中有一個對象序列V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,V[i-1]是已經排好序的對象。在插入V[i]時,利用二分搜索法尋找V[i]的插入位置。二分插入排序(BinaryInsertsort)基本思66二分插入排序二分插入排序67二分插入排序:分析二分搜索比順序搜索查找快,所以二分插入排序就平均性能來說比直接插入排序要快。它所需的排序碼比較次數與待排序對象序列的初始排列無關,僅依賴于對象個數。在插入第i個對象時,需要經過log2i+1次排序碼比較,才能確定它應插入的位置。因此,將n個對象(為推導方便,設為n=2k)用折半插入排序所進行的排序碼比較次數為二分插入排序是一個穩(wěn)定的排序方法。二分插入排序:分析二分搜索比順序搜索查找快,所以二分插入排序68當n較大時,總排序碼比較次數比直接插入排序的最壞情況要好得多,但比其最好情況要差。在對象的初始排列已經按排序碼排好序或接近有序時,直接插入排序比折半插入排序執(zhí)行的排序碼比較次數要少。折半插入排序的對象移動次數與直接插入排序相同,依賴于對象的初始排列當n較大時,總排序碼比較次數比直接插入排序的最壞情況要好得69使用鏈表插入排序每插入一個對象，最大排序碼比較次數等于鏈表中已排好序的對象個數最小排序碼比較次數為1

故總的排序碼比較次數最小為(n-1)最大為移動次數為0空間增加了指針域,和頭結點使用鏈表插入排序每插入一個對象，最大排序碼比較次數等于鏈表70交換排序交換排序71交換排序數據兩兩比較，逆序交換，直到全部有序冒泡，快速交換排序數據兩兩比較，逆序交換，直到全部有序72冒泡排序(BubbleSort)對象個數n。最多作最多作n-1趟，i=1,2,…,n-1i趟中從后向前j=n-1,n-2,……,i，順次兩兩比較比較如果發(fā)生逆序，則 交換V[j-1]和V[j]。冒泡排序(BubbleSort)對象個數n。最多作最多作73VoidBubbleSort(int*data,intn){ i=0;while(i<n-1){ last=n-1; for(j=n-1;j>i;j--) If(data[j]<data[j-1]){交換數據；last=j;}i=last; }}i是無序集的下界VoidBubbleSort(int*data,i74算法分析最好:n-1次比較,移動為0最壞需要一個附加空間穩(wěn)定算法分析最好:n-1次比較,移動為075快速排序基本思想：任選一個記錄，以其關鍵字為“樞軸”，序列中比它小的移動到該記錄之前，反之移動到它之后通過一趟排序將待排的記錄分割成兩個區(qū)域，一個區(qū)域中記錄的關鍵字比另一個區(qū)域的關鍵字小（一次劃分）然后左右兩邊分別處理直到排好快速排序基本思想：76快速排序劃分:pivotpos=low;pivot=D[low];for(i=low+1;i<=high;i++) if(D[i].Key<=pivot.Key&&++pivotpos!=i) D[pivotpos]和D[i]交換;D[pivotpos]和D[low]交換;快速排序劃分:77第7章-排序-Sorting第3章課件78第7章-排序-Sorting第3章課件79快速排序算法分析N個元素,排列有n!種,每個元素可以充當界點,界點的情況有n種平均時間復雜性:T(n)=cn+∑[T(k-1)+T(n-k)]/n,k=1:n設:T(0)=T(1)=b;T(n)=cn+2∑T(i)/n,i=0:n-1nT(n)=c(2n-1)+(n+1)T(n-1)T(n)<=2c(n+1)log(n+1)+b(n+1)/2快速排序算法分析N個元素,排列有n!種,每個元素可以充當界點80快速排序算法分析平均情況下,時間漸進復雜度是O(nlogn)，通常認為是在平均情況下的最佳排序.最壞情況:正序比較次數T(n)=(n-1)+(n-2)+…+1=n2/2,可以通過隨機選擇界點來避免將遞歸改為非遞歸快速排序算法分析平均情況下,時間漸進復雜度是O(nlogn)81快速排序算法分析空間最壞情況需要的棧O(n)可以通過先處理短的分段,來降低輔助空間到O(logn),當只有1個元素的時候不需要保存上下界,而非均勻分段時,下降的速度更快.不穩(wěn)定對于n較大的平均情況而言,快速排序是“快速”的,但是當n很小時,這種排序方法往往比其它簡單排序方法還要慢?？焖倥判蛩惴ǚ治隹臻g最壞情況需要的棧O(n)82上機練習:P171:插入排序P221:快速排序上機練習:P171:插入排序83第7章排序(2)第7章排序(2)84回顧排序的基本概念排序算法的分析插入排序(直接,二分)交換排序(冒泡,快速)回顧排序的基本概念85第7章-排序-Sorting第3章課件86內容提要插入排序(直接,二分)交換(冒泡,快速)選擇(selection,堆排序)歸并(merge)基數排序內容提要插入排序(直接,二分)87選擇排序N個元素,每次挑出最大或者最小,執(zhí)行(n-1)次循環(huán)選擇排序N個元素,每次挑出最大或者最小,執(zhí)行(n-1)次循環(huán)88第7章-排序-Sorting第3章課件89直接選擇排序的排序碼比較次數KCN與整個待排序對象序列象的初始排列無關。移動次數:最好:0最壞:3(n-1)穩(wěn)定直接選擇排序的排序碼比較次數KCN與整個待排序對象序列象的90堆排序樹性選擇排序堆的定義：n個元素的序列{k0，k1，……，kn-1}，當且僅當滿足以下關系時，稱之為堆最小化堆ki<=k2i+1ki<=k2i+2最大化堆Ki>=k2i+1ki>=k2i+2(i=0,1,2,……,(n-2)/2)最大化堆最大的結點一定出現在堆頂上。堆排序樹性選擇排序91歸并排序歸并，是將兩個或兩個以上的有序表合并成一個新的有序表。對象序列initList中兩個有序表V[1]…V[m]和V[m+1]…V[n]。它們可歸并成一個有序表,存于另一對象序列mergedList的V[1]…V[n]中。這種歸并方法稱為兩路歸并(2-waymerging)

歸并排序歸并，是將兩個或兩個以上的有序表合并成一個新的有序表92設變量i和j分別是表V[1]…V[m]和V[m+1]…V[n]的當前檢測指針。變量k是存放指針。設變量i和j分別是表V[1]…V[m]和V[m+1]93迭代的歸并排序算法

迭代的歸并排序算法就是利用兩路歸并過程進行排序的。其基本思想是：假設初始序列有n個對象，首先把它看n個長度為1的有序子序列,兩兩并歸,重復上述操作,直到得到一個序列.迭代的歸并排序算法

迭代的歸并排序算法就是利用兩路歸并過程進94算法分析輔助空間占用多穩(wěn)定算法分析輔助空間占用多95遞歸的表歸并排序

與快速排序類似，歸并排序也可以利用劃分為子序列的方法遞歸實現。在遞歸的歸并排序方法中，首先要把整個待排序序列劃分為兩個長度大致相等的部分,左子表和右子表。對子表分別遞歸地進行排序,然后再把排好序的兩個子表并歸.遞歸的表歸并排序

與快速排序類似，歸并排序也可以利用劃分為子96算法分析鏈表的歸并排序方法的遞歸深度為O(log2n)，對象排序碼的比較次數為O(nlog2n)。穩(wěn)定算法分析鏈表的歸并排序方法的遞歸深度為O(log2n)，對97基數排序不進行關鍵字的比較,而是利用”分配”和”收集”收集后的序列：2、52、5、7、17、18、9基數排序不進行關鍵字的比較,而是利用”分配”和”收集”98第7章-排序-Sorting第3章課件99空間：采用順序分配，顯然不合適。由于每個口袋都有可能存放所有的待排序的整數。所以，額外空間的需求為10n，太大了。采用鏈接分配是合理的。額外空間的需求為n，通常再增加指向每個口袋的首尾指針就可以了。在一般情況下，設每個鍵字的取值范圍為d,首尾指針共計2×r