数据结构与算法课件：Data Structure -Sorting.PPT

1、v概述概述v插入排序插入排序v快速排序快速排序v选择排序选择排序v归并排序归并排序v基数排序基数排序v各种内排方法比较各种内排方法比较第八章第八章 内部排序内部排序概 述n排序排序：将一个数据元素的任意序列，重新排列成将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。一个按关键字有序的序列。 n数据表数据表(datalist): 它是待排序数据对象的有限它是待排序数据对象的有限集合。集合。n主关键字主关键字(key): 数据对象有多个属性域数据对象有多个属性域, 即多即多个数据成员组成个数据成员组成, 其中有一个属性域可用来区分对其中有一个属性域可用来区分对象象, 作为排序依据，称为

2、关键字。也称为作为排序依据，称为关键字。也称为排序码排序码。n排序方法的稳定性排序方法的稳定性: 如果在对象序列中有两如果在对象序列中有两 个对象个对象ri和和rj, 它们的排序码它们的排序码 ki = kj , 且在排序之前且在排序之前, 对象对象ri排在排在rj前面。如果在前面。如果在排序之后排序之后, 对象对象ri仍在对象仍在对象rj的前面的前面, 则称则称这个排序方法是稳定的这个排序方法是稳定的, 否则称这个排序方法否则称这个排序方法是不稳定的。是不稳定的。n内排序与外排序内排序与外排序: 内排序是指在排序期间数内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指据对象全部存放

3、在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。在内、外存之间移动的排序。n排序的时间开销排序的时间开销: 排序的时间开销是衡量排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动可用算法执行中的数据比较次数与数据移动次数来衡量。次数来衡量。内排序分类内排序分类n依不同原则依不同原则插入排序插入排序、交换排序交换排序、选择排序选择排序、归归并排序并排序、和计数排

4、序等和计数排序等。n依所须工作量依所须工作量简单排序简单排序-时间复杂度时间复杂度o(n2)先进排序方法先进排序方法-时间复杂度时间复杂度o(n logn)基数排序基数排序-时间复杂度时间复杂度o(d.n)插入排序 (Insert Sorting)n基本思想基本思想 当插入第当插入第i (i 1) 个对象时个对象时, 前面前面的的V0, V1, , Vi-1已经排好序。这时已经排好序。这时, 用用Vi的排序码与的排序码与Vi-1, Vi-2, 的排序码的排序码顺序进行比较顺序进行比较, 找到插入位置即将找到插入位置即将Vi插入插入, 原来位置上的对象向后顺移。原来位置上的对象向后顺移。基本思想

5、基本思想 每步将一个待排序的对象每步将一个待排序的对象, 按其按其排序码大小排序码大小, 插入到前面已经排好序的一组插入到前面已经排好序的一组对象的适当位置上对象的适当位置上, 直到对象全部插入为止。直到对象全部插入为止。直接插入排序直接插入排序 (Insert Sort)直接插入直接插入排序过程排序过程0 1 2 3 4 5 temp i = 1i = 20 1 2 3 4 5 temp252525494949i = 3252525* * *i = 4i = 5161616161616080808Insertion Sort (2)template void inssort(Elem A,

6、int n) for (int i=1; i0) & (Comp:lt(Aj, Aj-1); j-) swap(A, j, j-1);Best Case:Worst Case:Average Case:直接插入排序的算法直接插入排序的算法typedef int SortData;void InsertSort ( SortData V , int n ) /按非递减顺序对表进行排序按非递减顺序对表进行排序 SortData temp; int i, j; for ( i = 1; i 0)&(tempVj-1; j- ) /从后向前顺序比较从后向前顺序比较 Vj = Vj- -1; Vj =

7、temp; 算法分析算法分析n设待排序对象个数为设待排序对象个数为 n, 则该算法的主程序则该算法的主程序执行执行n- -1趟。趟。n排序码比较次数和对象移动次数与对象排排序码比较次数和对象移动次数与对象排序码的初始排列有关。序码的初始排列有关。n最好情况下最好情况下, 排序前对象已按排序码从小排序前对象已按排序码从小到大有序到大有序, 每趟只需与前面有序对象序列每趟只需与前面有序对象序列的最后一个对象比较的最后一个对象比较1次次, 移动移动2次对象次对象, 总总的排序的排序 码比较次数为码比较次数为 n- -1, 对象移动次数对象移动次数为为 2(n- -1)。n最坏情况下最坏情况下, 第第

8、 i 趟时第趟时第 i 个对象必须与前面个对象必须与前面 i 个个对象都做排序码比较对象都做排序码比较, 并且每做并且每做1次比较就要做次比较就要做1次数据移动。则总排序码比较次数次数据移动。则总排序码比较次数KCN和对象移和对象移动次数动次数RMN分别为分别为n在平均情况下的排序码比较次数和对象移动次数在平均情况下的排序码比较次数和对象移动次数约为约为 n2/4。因此，直接插入排序的时间复杂度为。因此，直接插入排序的时间复杂度为 o(n2)。n直接插入排序是一种稳定的排序方法。直接插入排序是一种稳定的排序方法。111122142221nininnniRMNnnniKCN/)()( ,/)(2

9、2折半插入排序折半插入排序 (Binary Insertsort)基本思想基本思想 设在顺序表中有一设在顺序表中有一 个对象序列个对象序列 V0, V1, , Vn- -1。其中。其中, V0, V1, , Vi- -1 是已经排好序的对象。是已经排好序的对象。在插入在插入Vi 时时, 利用折半搜索法寻找利用折半搜索法寻找Vi 的插入位置。的插入位置。折半插入排序的算法折半插入排序的算法typedef int SortData; void BinInsSort ( SortData V , int n ) SortData temp; int Left, Right; for ( int i

10、= 1; i n; i+) Left = 0; Right = i- -1; temp = Vi; while ( Left = Right ) int mid = ( Left + Right )/2; if ( temp = Left; k- ) Vk+1 = Vk;/记录后移记录后移 VLeft = temp; /插入插入 折半插入排序0 1 2 3 4 5 temp i = 1i = 20 1 2 3 4 5 temp3 3 3i = 35 5 54 4 4i = 48 8 8i = 5161616n折半搜索比顺序搜索查找快折半搜索比顺序搜索查找快, 所以折半插入排序所以折半插入排序就

11、平均性能来说比直接插入排序要快。就平均性能来说比直接插入排序要快。n它所需的排序码比较次数与待排序对象序列的初它所需的排序码比较次数与待排序对象序列的初始排列无关始排列无关, 仅依赖于对象个数。在插入第仅依赖于对象个数。在插入第 i 个对个对象时象时, 需要经过需要经过 log2i +1 次排序码比较次排序码比较, 才能确才能确定它应插入的位置。因此定它应插入的位置。因此, 将将 n 个对象个对象(为推导方为推导方便便, 设为设为 n=2k )用折半插入排序所进行的排序码比用折半插入排序所进行的排序码比较次数为：较次数为： 1122log1logninni算法分析算法分析 n当当 n 较大时较

12、大时, 总排序码比较次数比直接插总排序码比较次数比直接插入排序的最坏情况要好得多入排序的最坏情况要好得多, 但比其最好情但比其最好情况要差。况要差。n在对象的初始排列已经按排序码排好序或在对象的初始排列已经按排序码排好序或接近有序时接近有序时, 直接插入排序比折半插入排序直接插入排序比折半插入排序执行的排序码比较次数要少。折半插入排执行的排序码比较次数要少。折半插入排序的对象移动次数与直接插入排序相同序的对象移动次数与直接插入排序相同, 依依赖于对象的初始排列。赖于对象的初始排列。n折半插入排序是一个稳定的排序方法。折半插入排序是一个稳定的排序方法。n折半插入排序的时间复杂度为折半插入排序的时

13、间复杂度为o(n2)。希尔排序希尔排序 (Shell Sort)n基本思想基本思想设待排序对象序列有设待排序对象序列有 n 个对象个对象, 首首先取一个整数先取一个整数 gap n 作为间隔作为间隔, 将全部对将全部对象分为象分为 gap 个子序列个子序列, 所有距离为所有距离为 gap 的的对象放在同一个子序列中对象放在同一个子序列中, 在每一个子序列在每一个子序列中分别施行直接插入排序。然后缩小间隔中分别施行直接插入排序。然后缩小间隔 gap, 例如取例如取 gap = gap/2 ，重复上述的子，重复上述的子序列划分和排序工作。直到最后取序列划分和排序工作。直到最后取 gap = 1,

14、将所有对象放在同一个序列中排序为止。将所有对象放在同一个序列中排序为止。n希尔排序方法又称为缩小增量排序。希尔排序方法又称为缩小增量排序。ShellsortShellsort/ Modified version of Insertion Sorttemplate void inssort2(Elem A, int n, int incr) for (int i=incr; i=incr)& (Comp:lt(Aj, Aj-incr); j-=incr) swap(A, j, j-incr);template void shellsort(Elem A, int n) /Shellsort fo

15、r (int i=n/2; i2; i/=2) /For each incr for (int j=0; ji; j+) / Sort sublists inssort2(&Aj, n-j, i); inssort2(A, n, 1);void ShellInsert(S_TBL &p，int dk) /*一趟增量为dk的插入排序，dk为步长因子*/for(i=dk+1；ilength；i+) if(p-elemi.key elemi-dk.key) p-elem0=p-elemi； /*为统一算法设置监测*/ for(j=i-dk；j0&p-elem0.key elemj.key；j=j-d

16、k)p-elemj+dk=p-elemj； p-elemj+dk=p-elem0； /*插入到正确位置*/void ShellSort(S_TBL *p，int dlta，int t) /*按增量序列dlta0，1，t-1对顺序表*p作希尔排序*/for(k=0；kt；t+)ShellSort(p，dltak)； /*一趟增量为dltak的插入排序*/n开始时开始时 gap 的值较大的值较大, 子序列中的对象较少子序列中的对象较少, 排序速度较快排序速度较快; 随着排序进展随着排序进展, gap 值逐渐变值逐渐变小小, 子序列中对象个数逐渐变多子序列中对象个数逐渐变多, 由于前面大由于前面大多

17、数对象已基本有序多数对象已基本有序, 所以排序速度仍然很快。所以排序速度仍然很快。nGap的取法有多种。的取法有多种。 shell 提出取提出取 gap = n/2 ，gap = gap/2 ，直到，直到gap = 1。n对特定的待排序对象序列，可以准确地估算排对特定的待排序对象序列，可以准确地估算排序码的比较次数和对象移动次数。序码的比较次数和对象移动次数。n希尔排序所需的比较次数和移动次数约为希尔排序所需的比较次数和移动次数约为n 1.3当当n趋于无穷时可减少到趋于无穷时可减少到n(log2 n)2快速排序快速排序 ( Exchange Sort )( Exchange Sort )n基本

18、方法基本方法设待排序对象序列中的对象个数为设待排序对象序列中的对象个数为n n。一般地，。一般地，第第i i趟起泡排序从趟起泡排序从1 1到到n-i+1n-i+1依次依次比较相邻两个记录地关键字，比较相邻两个记录地关键字，如果发生逆序，如果发生逆序，则交换之，其结果是这则交换之，其结果是这n-i+1n-i+1个记录中，关个记录中，关键字最大的记录被交换到第键字最大的记录被交换到第n-i+1n-i+1的位置上，的位置上，最多作最多作n-1n-1趟。趟。基本思想基本思想是两两比较待排序对象的排序码是两两比较待排序对象的排序码, ,如发生逆序如发生逆序( (即排列顺序与排序后的次序正好即排列顺序与排

19、序后的次序正好相反相反) )，则交换之，则交换之, ,直到所有对象都排好序为止。直到所有对象都排好序为止。起泡排序起泡排序 (Bubble Sort)Bubble Sort (1)Bubble Sort (2)template void bubsort(Elem A, int n) for (int i=0; ii; j-) if (Comp:lt(Aj, Aj-1) swap(A, j, j-1);Best Case:Worst Case:Average Case:快速排序快速排序 (Quick Sort)(Quick Sort)n基本思想基本思想是任取待排序对象序列中的某个对是任取待排序对

20、象序列中的某个对象象 (例如取第一个对象例如取第一个对象) 作为基准作为基准, 按照该对按照该对象的排序码大小象的排序码大小,将整个对象序列划分为左将整个对象序列划分为左右两个子序列：右两个子序列：u左侧子序列中所有对象的排序码都小于或左侧子序列中所有对象的排序码都小于或等于基准对象的排序码等于基准对象的排序码 u右侧子序列中所有对象的排序码都大于基右侧子序列中所有对象的排序码都大于基准对象的排序码准对象的排序码n基准对象则排在这两个子序列中间基准对象则排在这两个子序列中间(这也是这也是该对象最终应安放的位置该对象最终应安放的位置)。n然后分别对这两个子序列重复施行上述方然后分别对这两个子序列

21、重复施行上述方法，直到所有的对象都排在相应位置上为法，直到所有的对象都排在相应位置上为止。止。n基准对象也称为基准对象也称为枢轴（或支点）记录。枢轴（或支点）记录。Quicksorttemplate void qsort(Elem A, int i, int j) if (j = i) return; / List too small int pivotindex = findpivot(A, i, j); swap(A, pivotindex, j); / Put pivot at end / k will be first position on right side int k = pa

22、rtition(A, i-1, j, Aj); swap(A, k, j); / Put pivot in place qsort(A, i, k-1); qsort(A, k+1, j);template int findpivot(Elem A, int i, int j) return (i+j)/2; Quicksort Partitiontemplate int partition(Elem A, int l, int r, Elem& pivot) do / Move the bounds in until they meet while (Comp:lt(A+l, pivot);

23、 while (r != 0) & Comp:gt(A-r, pivot); swap(A, l, r); / Swap out-of-place values while (l r); / Stop when they cross swap(A, l, r); / Reverse last swap return l; / Return first pos on rightThe cost for partition is Q(n).Partition ExampleQuicksort Examplevoid QSort(Elem A ,int low,int high) if(lowhig

24、h)pivotloc=partition(A,low,high); QSort(A,low,pivotloc-1); /*对低子表递归排序对低子表递归排序*/ QSort(A,pivotloc+1,high); /*对高子表递归排序对高子表递归排序*/快速排序算法描述快速排序算法描述int Partition(Elem A ,int low,int high) Elem temp=Alow; pivotkey=Alow.key; while(lowhigu) while(low=pivotkey) high-;Alow=Ahigh; while(lowhigh&Ahigh.key=pivotk

25、ey) low+;Alow=Ahigh; Alow=temp; return low;快速排序的过程快速排序的过程初始关键字初始关键字prikey一次交换一次交换二次交换二次交换三次交换三次交换四次交换四次交换完成一趟排序完成一趟排序ijijjiijji ji完成一趟排序完成一趟排序分别进行快速排序分别进行快速排序有序序列有序序列练习：练习：n 49 14 38 74 96 65 8 49 55 27 Best CasennTnTTT)2/(2)(1) 1 ()0()log()(nnOnTWorst Case123456789 10 11123456789 10 1123456789 10 1

26、13456789 10 11456789 10 11nnTnTTT) 1()(1) 1 ()0(Worst-Case Analysis of QuicksortnnTnTTT) 1()(1) 1 ()0() 1()2() 1(nnTnT)2() 3()2(nnTnT)2() 1 ()2(. TTniiTnT2) 1 ()()(2nOAverage-Case Analysis of QuicksortnAssumptionuThe size of the first subarray is equally likely to be 0, 1, 2, ,n-1Fpi = 1/n for i=0,1

27、,n-1uPartitioning strategy preserves randomnessipninTiTnTTTi allfor y probabilit with) 1()()(1) 1 ()0(10)1()()(niiinTEiTEpnnTE10)1()()(niiinTEiTEpnnTE10)(2)(niiTEnnnTE210)(2)(niTEnTnEni) 12()(2)1() 1(220nniTEnTEnni12)1(2)1() 1()(nnTEnTEnnTnEnnTEnnTnE2)1() 1()(12)1(1)(nnnTEnnTE12)1(1)(nnnTEnnTEnnnTEn

28、nTE21)2()1(122)3(1)2(nnnTEnnTE322)1 (3)2(.TETE13122)1 (1)(niiTEnnTE)(log1)(nOnnTE)log()(nnOnTE n算法算法quicksort是一个递归的算法是一个递归的算法, 其递归树如图其递归树如图所示。所示。n算法算法partition利用序列第一个对象作为基利用序列第一个对象作为基准，将整个序列划分为左右两个子序列。准，将整个序列划分为左右两个子序列。算法中执行了一个循环算法中执行了一个循环, 只要是排序码小于只要是排序码小于基准对象排序码的对象都移到序列左侧基准对象排序码的对象都移到序列左侧, 最最后基准对象

29、安放到位后基准对象安放到位, 函数返回其位置。函数返回其位置。n快速排序是递归的，需要有一个栈存放每快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数。层递归调用时的指针和参数。n最大递归调用层次数与递归树的高度一致最大递归调用层次数与递归树的高度一致,理想理想情况为情况为 log2(n+1) 。因此，要求存储开销为。因此，要求存储开销为 O(log2n)。n在最坏的情况在最坏的情况, 即待排序对象序列已经按其排序即待排序对象序列已经按其排序码从小到大排好序的情况下码从小到大排好序的情况下, 其递归树成为单支其递归树成为单支树树, 每次划分只得到一个比上一次少一个对象的每次划分只得到

30、一个比上一次少一个对象的子序列。总的排序码比较次数将达子序列。总的排序码比较次数将达n快速排序是一种不稳定的排序方法。快速排序是一种不稳定的排序方法。2121211nnninni)()(基本思想基本思想 每一趟每一趟 (例如第例如第 i 趟趟, i = 0, 1, , n- -2) 在后面在后面 n- -i 个待排序个待排序记录中选出排序码最小的记录记录中选出排序码最小的记录, 作为作为有序序列中的第有序序列中的第 i 个记录。待到第个记录。待到第n- -2 趟作完趟作完, 待排序记录只剩下待排序记录只剩下1个个,就不用再选了。就不用再选了。选择排序Selection Sort (1)Sele

31、ction Sort (2)template void selsort(Elem A, int n) for (int i=0; ii; j-) / Find least if (Comp:lt(Aj, Alowindex) lowindex = j; / Put it in place swap(A, i, lowindex); Best Case:Worst Case:Average Case:n直接选择排序的排序码比较次数直接选择排序的排序码比较次数 KCN 与对象的初始排列与对象的初始排列无关。设整个待排序对象序列有无关。设整个待排序对象序列有 n 个对象个对象, 则第则第 i 趟选择

32、趟选择具有最小排序码对象所需的比较次数总是具有最小排序码对象所需的比较次数总是 n- -i- -1 次。总的次。总的排序码比较次数为排序码比较次数为20211ninninKCN)()(n对象的移动次数与对象序列的初始排列有关。当对象的移动次数与对象序列的初始排列有关。当这组对象的初始状态是按其排序码从小到大有序这组对象的初始状态是按其排序码从小到大有序的时候的时候, 对象的移动次数对象的移动次数RMN = 0，达到最少。，达到最少。n最坏情况是每一趟都要进行交换，总的对象移动最坏情况是每一趟都要进行交换，总的对象移动次数为次数为 RMN = n- -1。Heapsorttemplate voi

33、d heapsort(Elem A, int n) / Heapsort Elem mval; maxheap H(A, n, n); for (int i=0; in; i+) / Now sort H.removemax(mval); / Put max at endUse a max-heap, so that elements end up sorted within the array.Cost of heapsort:Cost of finding K largest elements:Heapsort Example (1)Heapsort Example (2)归并排序 (Me

34、rge Sort)n归并归并将两个或两个以上的有序表合并成一个新的将两个或两个以上的有序表合并成一个新的有序表。有序表。n两路归并两路归并 (2-way merging)原始序列原始序列initList 中两个有序表中两个有序表 initListl initListm和和initListm+1 initListn，它们可归并成一个有，它们可归并成一个有序表序表, 存于另一对象序列存于另一对象序列mergedList的的 l n 中。中。MergesortList mergesort(List inlist) if (inlist.length() = 1)return inlist; List

35、 l1 = half of the items from inlist; List l2 = other half of items from inlist; return merge(mergesort(l1), mergesort(l2);Mergesort Implementationtemplate void mergesort(Elem A, Elem temp, int left, int right) int mid = (left+right)/2; if (left = right) return; mergesort(A, temp, left, mid); mergeso

36、rt(A, temp, mid+1, right); for (int i=left; i=right; i+) / Copy tempi = Ai; int i1 = left; int i2 = mid + 1; for (int curr=left; curr right) / Right exhausted Acurr = tempi1+; else if (Comp:lt(tempi1, tempi2) Acurr = tempi1+; else Acurr = tempi2+;Optimized Mergesorttemplate void mergesort(Elem A, El

37、em temp, int left, int right) if (right-left) = THRESHOLD) inssort(&Aleft,right-left+1); return; int i, j, k, mid = (left+right)/2; if (left = right) return; mergesort(A, temp, left, mid); mergesort(A, temp, mid+1, right); for (i=mid; i=left; i-) tempi = Ai; for (j=1; j=right-mid; j+) tempright-j+1

38、= Aj+mid; for (i=left,j=right,k=left; k=right; k+) if (tempi tempj) Ak = tempi+; else Ak = tempj-;8 3 4 1 6 5 2 78 3 4 16 5 2 71 2 3 4 5 6 7 81 3 4 82 5 6 78 34 183413 81 4656 52 7275 62 7MergesortT(1) = O(1)T(n) = O(1)+2T(n/2)+O(n)T(n) = O(n log n)T(n/2)O(1)O(n)T(n/2)Analysis of MergesortnnTnTT)2/(

39、2)(1) 1 (nTnnTlog1) 1 ()(12/)2/()(nnTnnT11) 1 (2)2(.TT14/)4/(2/)2/(nnTnnT18/)8/(4/)4/(nnTnnT)log(log)(nnOnnnnTMergesortnO(n log n) worst-case running timenDivide-and-conquernCopying to and from temporary arrayuExtra memory requirementuExtra work08 21 25 25* 49 62 72 93 16 37 54 left mid mid+1 righti

40、nitList08 16 21 25 25* 37 49 54 62 72 93 left rightkmergeListn设变量设变量 i 和和 j 是表是表initListl m和和initList m+1 n的当前检测指针。的当前检测指针。k 是存放指针。是存放指针。u当当 i 和和 j 都在两个表的表长内变化时都在两个表的表长内变化时, 根据对根据对应项的排序码的大小应项的排序码的大小, 依次把排序码小的对依次把排序码小的对象排放到新表象排放到新表 k 所指位置所指位置中；中；u当当 i 与与 j 中有一个已经超出表长时，将另一中有一个已经超出表长时，将另一 个表中的剩余部分照抄到新表

41、中。个表中的剩余部分照抄到新表中。ijtypedef int SortData;void merge ( SortData InitList , SortData mergedList , int left, int mid, int right ) int i = left, j = mid+1, k = left; while ( i = mid & j = right ) /两两比较将较小的并入两两比较将较小的并入 if ( InitListi = InitListj ) mergedList k = InitListi; i+; k+; else mergedList k = Init

42、Listj; j+; k+; while ( i = mid ) mergedListk = InitListi; i+; k+; /将将mid前剩余前剩余的并入的并入 while ( j = right ) mergedListk = InitListj; j+; k+; /将将mid后剩后剩余的并入余的并入两路归并算法两路归并算法一趟归并排序的情形n设设initList0到到initListn-1中中 n 个对象已经分为个对象已经分为一些长度为一些长度为 len 的归并项的归并项, 将这些归并项两两归并将这些归并项两两归并, 归并成长度为归并成长度为 2len 的归并项的归并项, 结果放到

43、结果放到mergedList 中。中。n如果如果n不是不是2len的整数倍的整数倍, 则一趟归并到最后则一趟归并到最后,可能可能遇到两种情形：遇到两种情形：u 剩下一个长度为剩下一个长度为len的归并项和另一个长度的归并项和另一个长度不足不足len的归并项的归并项, 可用可用merge算法将它们归算法将它们归并成一个长度小于并成一个长度小于 2len 的归并项。的归并项。 u只剩下一个归并项，其长度小于或等于只剩下一个归并项，其长度小于或等于 len, 将它直接抄到将它直接抄到MergedList 中。中。迭代的归并排序算法n迭代的归并排序算法就是利用两路归并过程迭代的归并排序算法就是利用两路

44、归并过程进行排序的。其基本思想是：进行排序的。其基本思想是：n假设初始对象序列有假设初始对象序列有 n 个对象，首先把它看个对象，首先把它看成是成是 n 个长度为个长度为 1 的有序子序列的有序子序列 (归并项归并项)，先做两两归并，得到先做两两归并，得到 n / 2 个长度为个长度为 2 的归的归并项并项 (如果如果 n 为奇数，则最后一个有序子序为奇数，则最后一个有序子序列的长度为列的长度为1)；再做两两归并，；再做两两归并，如此重，如此重复，最后得到一个长度为复，最后得到一个长度为 n 的有序序列。的有序序列。vvoid MergePass ( SortData initList , S

45、ortData mergedList , int len ) int i = 0; while (i+2*len- -1 = n- -1) merge( initList, mergedList, i, i+len- -1, i+2*len- -1); i += 2 * len; /循环两两归并循环两两归并 if ( i+len = n- -1 ) merge( initList, mergedList, i, i+len- -1, n- -1); else for ( int j = i; j = n- -1; j+) mergedList j = initListj; v归并排序的主算法归

46、并排序的主算法void MergeSort ( SortData initList , int n ) /按对象排序码非递减的顺序对表中对象排序按对象排序码非递减的顺序对表中对象排序 SortData tempListn; int len = 1; while ( len n ) MergePass ( initList, tempList, len ); len *= 2;MergePass ( tempList, initList, len ); len *= 2; n在迭代的归并排序算法中在迭代的归并排序算法中, 函数函数MergePass( ) 做一做一趟 两 路 归 并 排 序趟 两

47、 路 归 并 排 序 , 要 调 用要 调 用 m e r g e ( ) 函 数函 数 n/(2*len) O(n/len) 次次, 函数函数MergeSort( )调用调用MergePass( )正好正好 log2n 次次,而每次而每次merge( )要执要执行比较行比较O(len)次次, 所以算法总的时间复杂度为所以算法总的时间复杂度为O(nlog2n)。n归并排序占用附加存储较多归并排序占用附加存储较多, 需要另外一个与原待需要另外一个与原待排序对象数组同样大小的辅助数组。这是这个算法排序对象数组同样大小的辅助数组。这是这个算法的缺点。的缺点。n归并排序是一个稳定的排序方法。归并排序是

48、一个稳定的排序方法。Binsort (1)A simple, efficient sort:for (i=0; in; i+) BAi = Ai;Ways to generalize:uMake each bin the head of a list.uAllow more keys than records.Binsort (2)template void binsort(Elem A, int n) List BMaxKeyValue; Elem item; for (i=0; in; i+) BAi.append(Ai); for (i=0; iMaxKeyValue; i+) for

49、(Bi.setStart(); Bi.getValue(item); Bi.next() output(item);Cost:基数排序基数排序多关键字排序多关键字排序例例 对对52张扑克牌按以下次序排序：张扑克牌按以下次序排序：23A23A23A23A两个关键字：花色两个关键字：花色（ ） 面值面值（23A）并且并且“花色花色”地位高于地位高于“面值面值”多关键字排序方法多关键字排序方法最高位优先法（最高位优先法（MSD)：先对最高位关键字先对最高位关键字k1（如如花色）排序，将序列分成若干子序列，每个子序列花色）排序，将序列分成若干子序列，每个子序列有相同的有相同的k1值；然后让每个子序列对

50、次关键字值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字重复，直至就每个子序列对最低位关键字kd排序；排序；最后将所有子序列依次连接在一起成为一个有序序最后将所有子序列依次连接在一起成为一个有序序列列最低位优先法最低位优先法(LSD)：从最低位关键字：从最低位关键字kd起进行排起进行排序，然后再对高一位的关键字排序，序，然后再对高一位的关键字排序，依次重依次重复，直至对最高位关键字复，直至对最高位关键字k1排序后，便成为一个排序后，便成为一个有序序列有序序列链式基数排序链式基数排序F基数