数据结构-10 内部排序

第10章 内部排序,10.1 概述 10.2 插入排序 10.3 快速排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 10.7 各种内部排序方法的比较讨论,排序就是将一组杂乱无章的数据按一定的规律顺次排列起来。 排序的目的是为了方便以后的查找。,10.1 概述,排序(Sorting)：简单地说，就是将一组记录按关键字域递增（由小到大）或递减（由大到小）的次序重新排列。 排序码（Sort Key）：作为排序依据的关键字。,有序表：排序后的结果。 无序表：排序前的状态。,升序表正序表：按排序码升序排列的有序表。 降序表逆序表：按排序码降序排列的有序表。,一、概念：,稳定排序：键值相同的记录，排序后相对次序总能保持不变。 不稳定排序：键值相同记录排序前后相对次序不能保持不变。,待排序列： 49,38,65,97,76,13,27,49 排序后:13,27,38,49,49,65,76,97 稳定 排序后:13,27,38,49,49,65,76,97不稳定,内排序：排序过程全部在内存中进行。 外排序：排序过程需要进行内存和外存之间的数据交换。,内排序,插入排序（直插排序、二分排序、希尔排序） 交换排序（冒泡排序、快速排序） 选择排序 （直选排序、树型排序、堆排序） 归并排序（二路归并排序、多路归并排序） 分配排序 （多关键字排序、基数排序）,无序区,有序区增长法：排序表可分成有序区和无序区，随着排序过程的进行，有序区逐渐增长，无序区逐渐缩小，最后全部为有序区，排序结束。初始有序区可为空或仅含一个元素，其余为无序区。,一趟排序,有序区,有序区,无序区,有序度增长法：排序表不能分成明显的有序区和无序区，但排序过程的每一步，整个排序表的有序程度都提高一点，最后变得完全有序。,评价标准： 1）时间； 2）附加空间。 3）算法的稳定性、复杂程度等 附加空间一般不大，排序经常执行，时间开销是最重标志。 两种基本操作： 1）比较：比较关键字的大小 2）移动：将记录从一个位置移动到另一个位置。 时间开销主要指关键字的比较次数和记录的移动次数。 当键值是字串时，比较要占用较多的时间；当记录很大时，交换记录时移动要占较多时间。 比较一般都需要，但移动可改变存储方式来避免。,二、时空分析：,1）顺序存储。对记录本身进行物理重排，移到合适的位置。 2）链式存储。无需移动记录，仅修改指针。（链）表排序。 3）索引顺序存储。对索引表物理重排，不移动原始记录本身。,三、存储方式,const int maxsize=100; /排序表容量，假设为100 typedef int datatype; /假设关键字为int typedef struct datatype key; /关键字域 othertype other; /其它域 rectype; /记录类型 typedef rectype listmaxsize+1; /排序表类型，0号单元不用（或作它用，如“监视哨”）,为简单起见，本章以数组作存储结构：,10.2 插入排序,基本思想 依次将待排记录插入到有序区适当位置，直到全部记录插入完毕； 初始有序区只有一个元素。,一、基本思想,每次将无序区第1条记录插入到有序区适当位置。初始取第1条记录为有序区，其它记录为无序区。随着排序进行，有序区不断扩大，无序区不断缩小。最终无序区为空，有序区包含了全部记录，排序结束。 有序区也可从排序表的尾部生成 。,10.2.1 直接插入排序 （Straight Insertion Sort）,例1：对(49 38 13 76 65 97 27 49 )直接插入排序。 初始：（49）38 13 76 27 49,（13 38 49 49 65 97）,（13 27 38 49 65 ）49,（13 38 49 76）27 49,（13 38 49 ）76 27 49,（38 49）13 76 27 49,为提高插入时的查找 效率，可以采用 折半查找 称为 折半插入排序,void InsertSort(list R,int n) /无监视哨 int i,j; NODE x; /x为中间结点变量 for(i=2;i=Ri-1.key) continue; x=Ri; /把待排记录赋给 x j=i-1; do /顺序比较和移动 Rj+1=Rj;j-; while(j0 /插入Ri ,二、算法实现,无序区第一记录Ri 插入有序区R1Ri1，找插入位置和移动记录交替进行：从有序区的后部j开始，如果该位置记录大于待插记录，则后移一位；待插记录插入到最后空出的位置上。,void InsertSort(list R,int n) /有监视哨 int i,j; for(i=2;i=Ri-1.key) continue; R0=Ri; /R0是监视哨 j=i-1; do /顺序比较和移动 Rj+1=Rj;j-; while(R0.keyRj.key); Rj+1=R0; /插入Ri ,R0为监视哨（Sentinel），省略下标越界检查“j0”：一旦越界，j=01，循环条件R0.keyRj.key不成立，自动控制while循环的结束。,初始：,i=3:,j=2:,j=1:,j=0:,例 有监视哨，第3趟,三、效率分析,时间： 最好：正序，n-1趟插入，每趟比较1次，移动0次： Cmin=n-1=O(n)，Mmin=0 最坏：逆序，每趟比较i-1次，移动i-1+2次。 平均： O(n2) 空间：一个辅助空间，用于交换（或监视哨） 。 稳定：相邻元素比较和移动 可用于链表 适用于基本(正向)有序或n较少的情况,一、基本思想,排序表分成若干组，相隔为某个“增量”的记录为一组，各组内直接插入排序；初始增量d1较大，分组较多（每组的记录数少），以后增量逐渐减少，分组减少（每组的记录数增多），直到最后增量为1（d1d2dt=1），所有记录放为同一组，再整体进行一次直接插入排序。 又称“缩小增量排序”（Diminishing Increment Sort） 。,10.2.2 希尔排序,例如，对（49,38,65,97,76,13,27,49）希尔排序。,初始关键字,d1=5,例如，对（49,38,65,97,76,13,27,49）希尔排序。,8,7,6,5,4,3,2,1,一趟排序结果,d1=3,例如，对（49,38,65,97,76,13,27,49）希尔排序。,8,7,6,5,4,3,2,1,二趟排序结果,d1=1,例如，对（49,38,65,97,76,13,27,49）希尔排序。,一趟排序结果,二趟排序结果,三趟排序结果,初始关键字,二、算法实现,void ShellInsert(list R,int n,int h) /一趟插入排序，h为本趟增量 int i,j,k; for(i=1;i=Rjh.key) continue; R0=Rj; /R0保存待插记录，但不是监视哨 k=jh; /待插记录的前一个记录 do /查找插入位置 Rk+h=Rk;k=kh;/后移记录，继续向前搜索 while(k0 /插入Rj ,两个for循环可合并为一个：for(j=1+h;j=n;j+)，相当于对每组交替直接插入排序。,void ShellSort(list R,int n,int d,int t) /d为增量序列，t为增量序列长度 int i; for(i=0;it;i+) /各趟插入排序 ShellInsert(R,n,di); ,希尔排序就是调用若干趟插入排序：,三、效率分析,时间：O(nlog2n)和O(n2)之间，大致O(n1.3) ，优于直接插入 其一，加速原理。相隔为增量的记录一组，组内移动一位，对原序列则移动若干位，加速向目标位置移动。开始时无序程度大，增量大，加速快；以后每个增量排序后，有序度提高一些，增量缩小，加速减缓。 其二，基本有序和小规模原理。开始时增量大，分组多，组内记录少，组内直接插入快；后来增量缩小，分组少，组内记录多，但有序性提高了，排序也较快。 不稳定：组内“相邻”移动，原序列则跳跃移动,10.3 交换排序,基本思想： 每次比较两个待排序的记录，如果关键字的次序与排序要求相反时就交换两者的位置，直到没有反序的记录为止。 特点： 键值较大的记录向排序表的一端移动，键值较小的记录向另一端移动。,一、基本思想,设排序表垂直放置，每个记录看作重量为键值的气泡；根据轻上重下原则，从下往上扫描，违反本原则的轻气泡，向上“飘浮”，如此反复，直到任何两个气泡都是轻上重下为止。 每一趟一个“最轻”的气泡冒到顶部上升法。 也可从上向下扫描，这时每一趟是一个“最重”的气泡沉到底部下沉法。 每次交换时，其中一个总沿着最终方向，另一个则未必（取决于上升法还是下降法）。,起泡排序（Bubble Sort）,例：对（49，38，65，97，76，13，27，49）冒泡排序。,void BubbleSort(list R,int n) /上升法冒泡排序 int i,j,flag; for(i=1;i=i+1;j) /从下向上扫描 if(Rj.keyRj1.key) /交换记录 flag=1; R0=Rj;Rj=Rj1;Rj1=R0; /交换，R0作辅助量 if(!flag) break; /本趟未交换过，排序结束 ,二、算法实现,排序中各元素不断接近自己的位置，如果一趟下来没有交换，则序列已经有序，可设一个标志flag判断，提前结束。,时间： 最好：初始正序，一趟排序，比较n-1次，移动0： Cmin=n-1=O(n)，Mmin=0： 最坏：初始逆序，n-1趟排序，每趟比较ni次，每次比较3次移动： 平均： O(n2) 辅助空间1，用于交换（用R0代替）。 稳定：只对相邻记录顺序比较和交换。 可用于链表（下沉法）,三、效率分析,例 链表起泡排序下沉法,15,35,25,h,45,q,p,15,35,h,25,45,end,end,h,15,25,35,45,end,NULL,搜索结束条件：p-next=end end初值为NULL，以后指向每趟最后点。,一、基本思想,任选一记录作基准，其它记录与之比较，小于等于放基准前面；大于等于放基准后面。 一趟排序后，左子序列小于等于基准，右子序列大于等于基准。对两子序列进行同样处理，直至每组只有1个记录，全部记录有序。 又称划分交换排序 可看成冒泡排序的改进：记录的比较和交换从两端向中间进行，较大的记录每次交换到较后位置，较小的交换到较前位置，每次移动距离较远，总的比较和移动次数较少。 是目前为止所有内排序中速度最快的一种。,快速排序（Quick Sorting）,1）一趟划分：,二、算法实现,设划分区间RpRq，指针i、j分别指向p、q。第1记录作基准 j从右向左扫描，找1个小于基准的记录Rj，移到位置i； i自i+1起从左向右扫描，找1个大于基准的记录Ri，移到位置j 再令j自j1起向左扫描， 如此交替改变扫描方向，从两端往中间靠拢，直至i=j时，i便是基准的最终位置，将它放在该处。,