• 1. 概述 插入排序 交换排序 选择排序 归并排序 基数排序 外排序 第九章 排序
  • 2. 什么是排序(Sorting)?简单地说,排序就是将一组杂乱无章的数据按一定的规律排列起来。 排序是计算机中经常遇到的操作。
  • 3. 排序的几个基本概念数据表(Data List) 待排序的数据对象的有限集合。 关键码(Key) 作为排序依据的数据对象中的属性域。 主关键码 不同的数据对象若关键码互不相同,则这种关键码称为主关键码。 排序的确切定义 使一组任意排列的对象变成一组按关键码线性有序的对象。
  • 4. 排序的几个基本概念排序算法的稳定性 判断标准:关键码相同的数据对象在排序过程中是否保持前后次序不变。如 2, 2*,1,排序后若为1, 2*, 2 则该排序方法是不稳定的。 内排序与外排序 区分标准:排序过程是否全部在内存进行。 排序的时间开销 它是衡量算法好坏的最重要的标志。通常用算法执行中的数据比较次数和数据移动次数来衡量
  • 5. 静态排序中的数据表的类定义const int DefaultSize = 100; Template class datalist; Templateclass Element{ friend calss datalist; private: Type key; field otherdata; } ; public: Type getKey( ) { return key;} void setKey(const Type x) {key=x;} Element&operator=(Element&x) {key=x->key;otherdata=x->otherdata;}
  • 6. Type operator == (Type &x) {return key==x->key;} Type operator <= (Type &x) {return key<=x->key; } Type operator >= (Type &x) {return key>=x->key; } Type operator < (Type &x) {return keykey; } templateclass datalist{ private: Element*Vector; int MaxSize,CurrentSize; int Partition(const int low,const int high) public; datalist (int MaxSz = DefaultSize):MaxSize( MaxSz) { }; void Swap(Element &x, Element &y) {Element temp=x;x=y;y=temp;} void Sort(); }
  • 7. 9.2 插入排序(Insert Sorting)基本原理,每步将一个待排序的对象,按其关键码大小,插入到前面已经排好序的一组对象适当位置上,直到对象全部插入为止。
  • 8. 三种常见的插入排序分类原理,根据往已经排好序的有序数据表中寻找插入位置的方法的不同而区分。 直接插入排序(Insert Sort) 折半插入排序(Binary Insert Sort) 链表插入排序 希尔排序(Shell Sort)
  • 9. 直接插入排序(Insert Sort)基本思想:当插入第i个对象时,前面的V[0],V[1],…,V[i-1]已经排好序,此时,用v[i]的关键码与V[i-1], V[i-2],…的关键码顺序进行比较,找到插入位置即将V[i]插入,原来位置上对象向后顺移。
  • 10. 直接插入排序举例i (0) (1) (2) (3) (4) (5) temp [21] 25 49 25* 16 08 25 1 [21 25] 49 25* 16 08 49 2 [21 25 49] 25* 16 08 25* 3 [21 25 25* 49] 16 08 16 4 [16 21 25 25* 49] 08 08 5 [08 16 21 25 25* 49]
  • 11. 直接插入排序程序Templatevoid dataList::sort{ Elementtemp;int j; for(int i=1;i0;j--) if (temp
  • 12. 直接插入排序的时间复杂度考虑关键码的比较次数和对象移动次数, 最好情况时两者分别为n-1与2(n-1),最坏情况时两者分别为 KCN=1+2+...+n-1 = n(n-1)/2 RMN= (1+2)+(2+2)+...+(n-1+2) = (n+4)(n-1)/2
  • 13. 直接插入排序的稳定性直接插入排序是一种稳定的排序方法。 原理:关键码相同的两个对象,在整个排序过程中,不会通过比较而相互交换。
  • 14. 折半插入排序(Binary Insert Sort)基本思想:当插入第i个对象时,前面的V[0],V[1],…,V[i-1]已经排好序,此时,用折半查找法寻找V[i]的插入位置移。
  • 15. 折半插入排序程序template void datalist ::sort(){ int left, right; Element temp; for (int i=1;i=left; k--) Vector[k+1]=Vector[k]; Vector[left] = temp; }
  • 16. 折半插入排序的时间复杂度考虑关键码的比较次数和对象移动次数 1. KCN 约为 n log 2 n,且与对象序列的初始排列无关 当n较大时,总关键码比较次数比直接插入排序的最坏情况要好得多,但比其最好情况时要差。 2. RMN与直接插入排序相同。
  • 17. 折半插入排序的稳定性折半插入排序是一种稳定的排序方法。 原理:关键码相同的两个对象,在整个排序过程中,不会通过比较而相互交换。
  • 18. 链表插入排序基本思想:用链表来表示已排序的数据对象,当插入V[i]时,依次在链表中检查,找到V[i]应插入的位置,并修改相应的链接指针。如此重复,直到V[n]也插入到链表中排好序为止。
  • 19. 链表插入排序的数据结构template class staticlinklist{ templateclass Element{ private: Type key; int link; public: Type getKey() {return key;} void setKey(const Type x) {key=x;} int getLink(){return link;} void setLink(const int ptr){link=ptr;} }
  • 20. 链表插入排序的数据结构templateclass staticlinklist{ private: Element * Vector; int MaxSize, CurrentSize; public: staticlinklist(int MaxSz=DefaultSize): MaxSize(MaxSize),CurrentSize(0){}; }
  • 21. 链表插入排序示例i index (0) (1) (2) (3) (4) (5) (6) key MaxNum 21 25 49 25* 16 8 link 1 0 0 0 0 0 0 2 link 1 2 0 0 0 0 0 3 link 1 2 3 0 0 0 0 4 link 1 2 4 0 3 0 0 5 link 5 2 4 0 3 1 0 6 link 6 2 4 0 3 1 5
  • 22. 链表插入排序的算法template int staticlinklist :: Sort(){ Vector[0].key=MaxNum; Vector[0].link=1; Vector[1].link=0; for(int i=2; i<=CurrentSize; i++){ int current =Vector[0].link; int pre = 0; while (Vector[current].key <= Vector[i].key) { pre=i; current=Vector[current].link;} Vector[i].link=current; Vector[pre].link=i; } }
  • 23. 链表插入排序的时间复杂度考虑关键码的比较次数和对象移动次数 1. KCN 最小为n-1,最大为 n (n-1)/2 2. 对象移动次数为0 。 链表插入排序方法是稳定的。
  • 24. 希尔排序1959年由D.L. Shell提出,又称缩小增量排序(Diminishing-increment sort) 。 基本思想:在插入排序中,只比较相邻的结点,一次比较最多把结点移动一个位置。如果对位置间隔较大距离的结点进行比较,使得结点在比较以后能够一次跨过较大的距离,这样就可以提高排序的速度。
  • 25. 希尔排序的基本过程设待排序的对象序列有n个对象,首先取一个整数gap
  • 26. 希尔排序示例i (0) (1) (2) (3) (4) (5) gap 21 25 49 25* 16 08 1 21 - - 25* 3 25 - - 16 49 - - 08 21 16 08 25* 25 49 2 21 - 08 - 25 2 16 - 25* - 49 08 16 21 25* 25 49 3 08 16 21 25* 25 49 1 08 16 21 25* 25 49
  • 27. 希尔排序的算法template void datalist ::sort(){ Elementtemp; int gap=CurrentSize/2,i,j; while(gap!=0) for (int i=gap; i< CurrentSize;i++){ temp = Vector[i]; for (j=i;j>=gap;j-=gap) if (temp
  • 28. 希尔排序中gap的取法Shell最初的方案是 gap= n/2, gap=gap/2,直到gap=1. Knuth的方案是gap = gap/3+1 其它方案有,都取奇数为好;或gap互质为好等等。
  • 29. 希尔排序的时间复杂度对希尔排序的复杂度的分析很困难,在特定情况下可以准确地估算关键码的比较和对象移动次数,但是考虑到与增量之间的依赖关系,并要给出完整的数学分析,目前还做不到。 Knuth的统计结论是,平均比较次数和对象平均移动次数在n1.25 与1.6n1.25之间。 希尔排序的稳定性 希尔排序是一种不稳定的排序方法。 如序列 3 2 2* 5
  • 30. 9.3 交换排序基本原理,两两比较待排序的对象的关键码,如果发生逆序,则交换之,直到全部对象都排好序为止。 两种常见的交换排序 起泡排序(Bubble Sort) 快速排序(Quick Sort)
  • 31. 起泡排序的基本过程假设待排序的n个对象的序列为V[0],V[1],..., V[n-1],起始时排序范围是从V[0]到V[n-1] 在当前的排序范围之内,自右至左对相邻的两个结点依次进行比较,让值较大的结点往下移(下沉),让值较小的结点往上移(上冒)。每趟起泡都能保证值最小的结点上移至最左边,下一遍的排序范围为从下一结点到V[n-1]。 在整个排序过程中,最多执行(n-1)遍。但执行的遍数可能少于(n-1),这是因为在执行某一遍的各次比较没有出现结点交换时,就不用进行下一遍的比较。
  • 32. 起泡排序示例i (0) (1) (2) (3) (4) (5) 21 25 49 25* 16 08 1 08 21 25 49 25* 16 2 08 16 21 25 49 25* 3 08 16 21 25 25* 49 4 08 16 21 25 25* 49
  • 33. 起泡排序的算法Templatevoid datalist::sort(){ int pass=1;int exchange=1; while (pass=pass;j--) if (Vector[j-1]>Vector[j]){ swap(Vector[j-1],vector[j]) exchange=1; } pass++; } }
  • 34. 起泡排序的时间复杂度考虑关键码的比较次数和对象移动次数 1. KCN 为 n * (n-1) /2 2. RMN 为 3/2 * n* (n-1) 。 起泡排序方法是稳定的。
  • 35. 快速排序的基本过程快速排序法是一种所需比较次数较少,目前在内部排序中速度较快的方法。 其思想是取待排序的结点序列中某个结点的值作为控制值,采用某种方法把这个结点放到适当的位置,使得这个位置的左边的所有结点的值都小于等于这个控制值,而这个位置的右边的所有结点的值都大于等于这个控制值。然后分别对这两个子序列重复实施上述方法.
  • 36. 快速排序示例i (0) (1) (2) (3) (4) (5) pivot(基准) 21 25 49 25* 16 08 21 1 08 16 21 25* 25 49 08(左),25*(右) 2 08 16 21 25* 25 49 25(右) 3 08 16 21 25* 25 49 4 08 16 21 25* 25 49
  • 37. 快速排序的递归算法template void QuickSort( const int left, const int right) { if (leftright) QuickSort(list,pivotpos+1,right); }
  • 38. 快速排序的递归算法template int Partition( const int low, const int high){ int pivotpos = low; Element pivot = Vector[low]; for (int i=low+1; i<=high; i++) if(Vector[i]
  • 39. 快速排序的时间复杂度考虑关键码的比较次数和对象移动次数 1. 平均计算时间为O(n*log2n) ,实验表明,快速排序是我们所讨论过的内排序中,平均计算时间最快。 2. 最坏情况总的关键码比较次数为 n* (n-1) /2,例如,对一个已经排序的序列进行快速排序。 快速排序是不稳定的排序方法。 如序列2, 3, 3*, 1
  • 40. 9.4 选择排序基本原理,将待排序的结点分为已排序(初始为空)和为未排序两组,依次将未排序的结点中值最小的结点插入已排序的组中。
  • 41. 三种常见的选择排序 直接选择排序 锦标赛排序 堆排序
  • 42. 直接选择排序的基本过程在一组对象V[i]到V[n-1]中选择具有最小关键码的对象 若它不是这组对象中的第一个对象,则将它与这组对象中的第一个对象对调。 删除具有最小关键码的对象,在剩下的对象中重复第(1)、(2)步,直到剩余对象只有一个为止。
  • 43. 直接选择排序示例i (0) (1) (2) (3) (4) (5) k [21 25 49 25* 16 08] 5 0 08 [25 49 25* 16 21] 4 1 08 16 [49 25* 25 21] 5 2 08 16 21 [25* 25 49] 3 3 08 16 21 25* [25 49] 4 4 08 16 21 25* 25 [49]
  • 44. 直接选择排序的算法template void datalist :: sort() { for(int i=0;i
  • 45. 直接选择排序的时间复杂度考虑关键码的比较次数和对象移动次数 1. KCN与对象的初始排列无关,总为 n* (n-1) /2 2. RMN与对象的初始排列有关,最少为0,最大为3(n-1) 。如:n-1,0,1,2,..., n-2 直接选择排序是不稳定的排序方法。
  • 46. 锦标赛排序的基本过程在一组对象V[i]到V[n-1]中选择具有最小关键码的对象 若它不是这组对象中的第一个对象,则将它与这组对象中的第一个对象对调。 删除具有最小关键码的对象,在剩下的对象中重复第(1)、(2)步,直到剩余对象只有一个为止。
  • 47. 锦标赛排序示例i (0) (1) (2) (3) (4) (5) (6) 21 25 49 25* 16 08 63 ? 21 25* 08 63 21 08 08 21 25 49 25* 16 08 63 ? 21 25* 16 63 21 16 16
  • 48. 锦标赛排序的算法template class DataNode{ public: Type data; int index; int active; } template void TournamentSort( Type a[ ], int n){ DataNode *tree; DataNode item; int bottonRowSize = PowerOfTwo(n); int TreeSize = 2* bottomRowSize –1; int loadindex = bottomRowSize –1; tree = new DataNode [TreeSize];
  • 49. int j=0; for (int i= loadindex; i
  • 50. for (i=0; i void UpdateTree (DataNode *tree, int i) { if ( i %2 == 0) tree[(i-1)/2] = tree[i-1]; else tree[(i-1)/2] = tree[i+1]; i=(i-1)/2;
  • 51. while (i) { if ( i % 2 == 0) j= i-1; else j=i+1; if (! tree[i].active || ! tree[j].active) if ( tree[i].active) tree[(i-1)/2] = tree[i]; else tree[(i-1)/2] = tree[j]; else if ( tree[i].data < tree[j].data) tree[(i-1)/2] = tree[i]; else tree[(i-1)/2] = tree[j]; i = (i-1)/2; } }
  • 52. 锦标赛排序的时间复杂度考虑关键码的比较次数和对象移动次数 1. 比较次数为 O(log2n) 2. 对象的移动次数不超过比较次数。 所以总的时间复杂度为O(n log2n) 锦标赛排序是稳定的排序方法。
  • 53. 堆排序利用第6章介绍的堆及其运算,可以方便地实现选择排序的思路。 堆排序分为两个步骤: 根据初始输入,形成初始堆。 通过一系列的对象交换和重新调整进行排序。
  • 54. 堆的定义完全二叉树的数组表示 Ki  K2i+1 && Ki  K2i+2 Ki  K2i+1 && Ki  K2i+2
  • 55. 堆排序示例i (0) (1) (2) (3) (4) (5) 21 25 49 25* 16 08 初始堆为: 21 25 49 25* 16 08 调整后的最大堆为: 49 25 21 25* 16 08
  • 56. 堆排序示例(续) 交换0号与5号元素后为: 08 25 21 25* 16 49 调整后的堆为: 25 25* 21 08 16
  • 57. 最大堆的向下调整算法 template void MaxHeap:: FilterDown (const int i,const int EndOfHeap ){ int current = i; int child = 2*i+1; Type temp = heap[i]; while ( child <= EndOfHeap ) { if ( child+1 < EndOfHeap && heap[child]= heap[child]) break; else {heap[current] = heap[child]; current = child; child = 2 * child +1;} } heap[current] = temp; }
  • 58. 堆排序的算法 template void datalist ::sort() { for (int i=(CurrentSize –1)/2; i>=0; i--) FilterDown(i, CurrentSize-1); for (int i=(CurrentSize –1); i>=1; i--) { Swap( heap[0], heap[i]); FilterDown(0,i-1); }
  • 59. 堆排序的时间复杂度堆排序的时间复杂性为O(n log2n) 空间复杂性为 O(1) 堆排序是不稳定的排序方法。
  • 60. 9.5 归并排序基本原理,通过对两个或两个以上的有序结点序列的合并来实现排序。 如果是对两个已经排好序的序列的合并来实现排序,称为“两路归并”(2-way merging) 。
  • 61. 两路归并的基本思想设有两个有序表A和B,对象个数分别为al和bl,变量i和j分别是两表的当前指针。设表C是归并后的新有序表,变量k是它的当前指针。i和j对A和B遍历时,依次将关键码小的对象放到C中,当A或B遍历结束时,将另一个表的剩余部分照抄到新表中。
  • 62. 两路归并的示例 initList 08 21 25 25* 49 62 72 93 16 37 54 归并后为 mergedList 08 16 21 25 25* 37 49 54 62 72 93
  • 63. 两路归并的算法template void merge( datalist &mergedList, const int left, const int mid, const int right) { int i=left; j=mid+1; k=left; while(i<=m && j<=n) if (Vector[i]
  • 64. 两种常见的归并排序 迭代的归并排序算法 递归的表归并排序
  • 65. 迭代的归并排序假设初始的对象序列有n个对象,我们首先把它看成是n个长度为1的有序子序列,先做两两归并,得到n/2个长度为2的归并项(如果n为奇数,则最后一个有序子序列的长度为1);再做两两归并,……,如此重复,最后得到一个长度为n的有序序列。
  • 66. 归并排序的过程
  • 67. 算法template void MergePass( datalist &mergedList, const int len) { int i=0; while(i+2*len <= CurrentSize-1) { merge(mergedList,i, i+len-1, i+2*len-1); i+=2*len; } if (I+len<=CurrentSize-1) else for(int j=i;j<=CurrentSize-1;j++) mergedlist.Vector[j]=Vector[j];
  • 68. 迭代的归并排序的时间复杂度MergeSort调用 log2n 次,总的时间复杂度为O(n log2n) 空间开销为需要一个与原待排序对象数组同样大小的辅助数组。 迭代的归并排序是稳定的排序方法。
  • 69. 递归的表归并排序首先把整个待排序序列划分为两个长度大致相等的部分,分别称为左子表和右子表。对这些子表分别递归地进行排序,然后再把排好序的两个子表进行归并。
  • 70. 递归的表归并的示例
  • 71. 存储表示的选择 在归并时,若采用基于数组的两路归并算法,由于需要进行数组元素的传递,影响了归并的效率。 若对排序的对象采用静态链表的存储表示,则可以得到一种有效的归并排序算法。
  • 72. 静态链表的数据结构同链表插入排序中的数据结构 template class staticlinklist{ private: struct Element{ Type key; field otherdata; int link; public: Type getKey() {return key;} void setKey(const Type x) {key=x;} void operator = (Element &item) { this = item; }
  • 73. void Swap(Element &x, Element &y) {Element temp=x; x=y; y=temp;} } public: staticlinklist(int MaxSz=DefaultSize): MaxSize(MaxSize){}; void MakEmpty() {Vector[0].link=0; CurrentSize=0;} private: Element * Vector; int MaxSize, CurrentSize; }
  • 74. 静态链表的数据结构 初始时,置所有的Vector[i].link = 0,即每个链表结点都是一个独立的单链表。函数ListMerge()将两个有序单链表归并为一个单链表的算法。
  • 75. 链表的归并算法template int staticlinklist::ListMerge ( const int start1, const int start2) { int k=0, i=start1, j=start2; while(i!=0 && j!=0) if (Vector[i].key <= Vector[j].key) { Vector[k].link=i;k=i;i=Vector[i].link;} else {Vector[k].key=j; k=j; j= Vector[j].link;}
  • 76. if (i==0)Vector[k].link=j; else list.Vector[k].link=i; return list.Vector[0].link; } template int staticlinklist ::sort(int left, int right) { if ( left >= right ) return left; int middle = (left + right) / 2; return ListMerge (sort(left,middle), sort(middle+1,right)); }
  • 77. 链表的归并排序的时间复杂度递归深度为O(log2n),总的时间复杂度为O(n log2n) 对象的移动次数为0 链表的归并排序是稳定的排序方法。
  • 78. 9.6 基数排序基本原理,采用“分配”和“收集”的办法,用对多关键码进行排序的思想实现对单关键码进行排序的方法。 下面先介绍多关键码排序
  • 79. 多关键码排序方法示例如对扑克牌的排序 每张扑克牌有两个“关键码”: 花色和面值 它们之间有次序的优先。 对以上排序,可以先对花色排序,或先对面值排序。
  • 80. 多关键码有序的概念考虑对象序列{V0,V1,..., Vn-1},每个对象Vi含d个关键码(Ki1,Ki2,..., Kid)。若对序列中的任意两个对象Vi和Vj都有 (Ki1,Ki2,..., Kid) < (Kj1,Kj2,..., Kjd) 则称序列对关键码(Ki1,Ki2,..., Kid)有序,且K1称为最高位关键码,Kd称为最低位关键码。
  • 81. 多关键码排序原理:根据组成关键码的各位的值进行排序。 实现基数排序的两种方法: 1 最高位优先(MSD)排序:从关键码的高位到低位 2 最低位优先(LSD)排序:从关键码的低位到高位 MSD方法通常是一个递归的过程。
  • 82. 多关键码排序(续)LSD和MSD方法也可应用于对一个关键码进行的排序。此时可将单关键码Ki看成是一个子关键码组: (Ki1,Ki2,..., Kid) 如对关键码取值范围为0到999的一组对象,可看成是(K1,K2,K3)的组合。 MSD方法按K1,K2,K3的顺序对所有对象排序;LSD方法按K3 ,K2 , K1的顺序对所有对象排序。
  • 83. 链式的基数排序基数排序是一种典型的LSD排序方法,它利用“分配”和“收集”两种运算对单关键码进行排序。 此时可将单关键码K看成是一个子关键码组: (Ki1,Ki2,..., Kid) 排序过程:设关键码共有d位,让j= d, d-1,...,1, 依次执行d次“分配”与“收集”。