1、第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不稳定,内排序:排序过程全部在内存中进行。 外排序:排序过程需要进行内存和外存之间的数据交换。,内排序,插入排序(直插排序、二
2、分排序、希尔排序) 交换排序(冒泡排序、快速排序) 选择排序 (直选排序、树型排序、堆排序) 归并排序(二路归并排序、多路归并排序) 分配排序 (多关键字排序、基数排序),无序区,有序区增长法:排序表可分成有序区和无序区,随着排序过程的进行,有序区逐渐增长,无序区逐渐缩小,最后全部为有序区,排序结束。初始有序区可为空或仅含一个元素,其余为无序区。,一趟排序,有序区,有序区,无序区,有序度增长法:排序表不能分成明显的有序区和无序区,但排序过程的每一步,整个排序表的有序程度都提高一点,最后变得完全有序。,评价标准: 1)时间; 2)附加空间。 3)算法的稳定性、复杂程度等 附加空间一般不大,排序经常执行,时间开销是最重标志。 两种基本操作: 1)比较:比较关键字的大小 2)移动:将记录从一个位置移动到另一个位置。 时间开销主要指关键字的比较次数和记录的移动次数。 当键值是字串时,比较要占用较多的时间;当记录很大时,交换记录时移动要占较多时间。 比较一般都需要,但移动可改变存储方式来避免。,二、时空分析:,1)顺序存储。对记录本身进行物理重排,移到合适的位置。 2)链式存储。无需移动记录,仅
3、修改指针。(链)表排序。 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
4、 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
5、; /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 I
6、ncrement 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+),相当于对每组交替直接插
7、入排序。,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 交换排序,基本思想: 每次比较两个待排序的记录,如果关键字的次序与排序要求相反时就交换两者的位置,直到没有反序的记录为止。 特点: 键值较大的记录向排序表的一端移动,键值较小的记录向另一端移动。,一、基本思想,设排序表垂直放置,每个记录看作重量为键值的气泡;根据
8、轻上重下原则,从下往上扫描,违反本原则的轻气泡,向上“飘浮”,如此反复,直到任何两个气泡都是轻上重下为止。 每一趟一个“最轻”的气泡冒到顶部上升法。 也可从上向下扫描,这时每一趟是一个“最重”的气泡沉到底部下沉法。 每次交换时,其中一个总沿着最终方向,另一个则未必(取决于上升法还是下降法)。,起泡排序(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趟排序,每
9、趟比较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便是基准的最终位置,将它放在该处。,
《数据结构-10 内部排序》由会员ldj****22分享,可在线阅读,更多相关《数据结构-10 内部排序》请在金锄头文库上搜索。