数据结构第8章_排序.pptVIP

第8章 排序 8.1 排序基本概念 8.2 插入类排序 8.3 交换类排序 8.4 选择类排序 8.5 归并排序 8.6 基数排序 8.7 各类排序方法的比较 8.8 外部排序 排序： 将一组杂乱无章的数据元素(记录) 按关键字升序(或降序)重新排列的过程 1. 内排序与外排序: 内排序：在排序期间数据对象全部存放在内存的排序； 外排序：在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。 在排序过程中，一般进行两种基本操作： (1)比较两个关键字的大小；对排序方法是必要的 (2)将记录从一个位置移动到另一个位置。采用适当的存储方式予以避免 对于待排序的记录序列，有三种常见的存储表示方法： 向量结构 链表结构 记录向量与地址向量结合 链表结构：记录之间逻辑上的相邻性靠指针维持，不用移动记录元素，而只需要修改指针 记录向量与地址向量相结合 本章内容主要讨论在向量结构上各种排序方法的实现 假设待排记录的关键字为整数，从数组下标为1的位置开始存储，下标为0的位置存储监视哨或空闲不用 #define Maxsize 100//设待排序记录最多为100个元素 typedef int KeyType; //假设待排序记录关键字的数据类型为整型 typedef struct { KeyType key; OtherType other_data; //待排序记录中的其他数据类型 } RecordType; RecordType r[Maxsize] 第8章 排序 8.1 排序基本概念 8.2 插入类排序 8.3 交换类排序 8.4 选择类排序 8.5 归并排序 8.6 基数排序 8.7 各类排序方法的比较 8.8 外部排序 插入排序的基本思想： 从数组的第2号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上 8.2.1 直接插入排序 基本思想：当插入第i (i ? 1) 个对象时，前面的v[0], v[1], …, v[i-1]已经排好序。这时，用v[i]的关键字与v[i-1], v[i-2], …的关键码顺序进行比较，找到插入位置即将v[i]插入，原来位置上的对象向后顺移。 直接插入排序 void InsSort(RecordType r[], int length) /*对记录数组r做直接插入排序，length为数组的长度*/ { for(i=2;ilength+1;i++) { r[0]=r[i]; j=i-1; /*将待插入记录存放到变量x中*/ while(r[0].keyr[j].key) /*寻找插入位置*/ { r[j+1]=r[j]; j=j-1; } r[j+1]=r[0]; /*将待插入记录插入到已排序的序列中*/ } } /*InsSort*/ 直接插入类排序分析 平均时间复杂度：O(n2) 稳定性：稳定的排序方法 算法分析 最好情况下，排序前对象已经按关键码大小从小到大有序，每趟只需与前面的有序对象序列的最后一个对象的关键码比较 1 次，移动 2 次对象，总的关键码比较次数为 n-1，对象移动次数为 2(n-1)。 最坏情况下，第 i 趟时第 i 个对象必须与前面 i 个对象都做关键码比较，并且每做 1 次比较就要做 1 次数据移动。则总的关键码比较次数KCN和对象移动次数RMN分别为 8.2.2 希尔排序 希尔排序方法/缩小增量排序的基本思想：设待排序对象序列有 n 个对象，首先取一个整数 gap n 作为间隔，将全部对象分为 gap 个子序列，所有距离为 gap 的对象放在同一个子序列中，在每一个子序列中分别施行直接插入排序。然后缩小间隔 gap，例如取 gap = ?gap/2?，重复上述的子序列划分和排序工作。直到最后取 gap == 1，将所有对象放在同一个序列中排序为止。 开始时 gap 的值较大，子序列中的对象较少，排序速度较快；随着排序进展，gap 值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。 希尔排序 void ShellInsert(RecordType r[], int length，int delta) /