序选择排序归并排序基数排序内部排序比较外排序.pptVIP

基本概念 插入排序 交换排序 选择排序 归并排序 基数排序 内部排序比较 外排序 ;关键字 假设被排序的对象是由一组记录组成的文件，记录由若干个数据项(或域)组成，其中有一项可用来标识一个记录，称为关键字项。该数据项的值称为关键字(Key)。在不易产生混淆时，本章中将关键字项简称为关键字。 排序 所谓排序（Sort），就是要整理文件中的记录，使它们按关键字递增(或递减)次序重新排列。 排序方法的稳定性在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称该排序方法是稳定的；否则，若具有相同关键字的记录之间的相对次序发生变化，则称该排序方法是不稳定的。;排序方法的分类 按是否涉及数据的内、外存交换分类： 外排序、内排序。 按策略划分内部排序方法： 插入排序、选择排序、交换排序、归并排序和基数排序等。 排序算法性能评价 评价排序算法好坏的标准主要有两条： （1）执行算法所需的时间； （2）执行算法所需的辅助空间。 ;不同存储方式的排序过程 以顺序表作为存储结构： 对记录本身进行物理重排。 以链表作为存储结构： 无须移动记录，仅需修改指针。 用顺序的方式存储待排序的记录，但同 时建立一个辅助表。 只需对辅助表的表目进行物理重排，适 用于难以在链表上实现，仍需避免排序 过程中移动记录的排序方法。 ; 若无特别说明，则所讨论排序均为升序（即按递增排序），并以记录数组作为文件的存储结构。同时假定关键字是整数。记录数组的类型说明如下： typedef int KeyType； typedef struct { KeyType key； InfoType otherinfo； }RecType； typedef RecType SeqList[n+1]；;9.2 插入排序;9.2.1 直接插入排序;例9.1 直接插入排序举例;直接插入排序算法 void lnsertSort(SeqList R) { int i,j; for (i=2;in;i++) {R[0]＝R[i]; j＝i-1; while (R[0].keyR[j].key) {R[j+1]＝R[j]; j- -; } R[j+1]＝R[0]; } }; 算法中引入附加记录R[0]有两个作用：　　①进入查找循环之前，它保存了R[i]的副本，使得不至于因记录的后移而丢失R[i]中的内容； 　　②在while循环“监视”下标变量j是否越界，一旦越界（即j=0），能自动控制while循环的结束，从而避免了在while循环内的每一次都要检测j是否越界（即省略了循环条件j=1）。 因此，我们把R[0]称为“监视哨”。;直接插入排序的算法分析;9.2.2 希尔排序;希尔排序的基本过程;希尔排序示例;希尔排序算法 void ShellPass(SeqList R，int d) { for(i=d+1；i=n；i++) if(R[i].keyR[i-d].key) { R[0]=R[i];j=i-d； do { R[j+d]=R[j]； j=j-d； }while(j0R[0].keyR[j].key)； R[j+d]=R[0]； } } ; 为什么shell排序的时间性能优于直接插入排序呢？ 因为直接插入排序在初态为正序时所需时间最少，实际上，初态为基本有序时直接插入排序所需的比较和移动次数均较少。另一方面，当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n2)差别不大。在shell排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但组内元素已经过多次排序，数组已经比较接近有序状态，所以新的一趟排序过程也较块。;希尔排序中增量di的取法;希尔排序的算法分析;9.3 交换排序;9.3.1 冒泡排序;例9.3 冒泡排序示例;冒泡排序算法 void BubbleSort(SeqList R) {int i，j，exchange； for(i=1;in;i++) { exchange=0； for(j=n-1;j=i；j--) if(R[j+1].keyR[j].key) { R[0]=R[j+1]； R[j+1]=R[j]； R[j]=R