《第十章A插入排序》-课件.ppt

18 第十章 内部排序 * * ￡10.1 概述 ￡10.2 插入排序 ￡10.2.1 直接插入排序 ￡10.2.2 其他插入排序 ￡10.2.3 希尔排序 ￡10.3 快速排序 ￡10.4 选择排序 ￡10.4.1 简单选择排序 ￡10.4.2 树形选择排序 ￡10.4.3 堆排序 ￡10.5 归并排序 ￡10.6 基数排序 ￡10.6.1 多关键字的排序 ￡10.6.2 链式基数排序 ￡10.7 各种内部排序方法的比较讨论 （1）相关术语 假设含有n个记录的序列为 {R1, R2, … , Rn} （10 —1） 其相应的关键字序列为 {K1, K2, … , Kn} 需确定1, 2, … , n的一种排列p1, p2, … , pn，使其相应的关键字满足如下的非递 减（或非递增）关系 （10 — 2） 即使式（10—1）的序列成为一个按关键字有序的序列 （10 — 3） 这样一种操作称为排序。 ￡10.1 概述 例如：将下列关键字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 调整为 14, 23, 36, 49, 52, 58, 61 ,75, 80, 97 假设Ki = Kj(1≤i≤n, 1≤j≤n, i≠j)(此时Ki和Kj是记录的次关键字)，且在排 序前的序列中Ri领先于Rj（即i j）。 若在排序后的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的； 若可能使排序后的序列中Rj领先于Ri，则称所用的排序方法是不稳定的。 ￡10.1 概述 如 2, 2*,1，排序后若为1, 2*, 2 则该排序方法是不稳定. 内部排序：指的是待排序记录存放在计算机随机存储器中进行的排序过程。 外部排序：指的是待排序记录的数量很大，以致内存一次不能容纳全部记录， 在排序过程中尚需对外存进行访问的排序过程。 ￡10.1 概述 （2）内部排序的分类 ①按排序过程中依据的不同原则： 1.插入排序； 将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度； 2.交换排序； 通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度; 3.选择排序； 从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度; 4.归并排序； 通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度; （2）内部排序的分类 ②按排序过程中所需的工作量： 1．简单的排序方法， 其时间复杂度为O(n2)； 2．先进的排序方法，其时间复杂度为O(nlogn)； 3．基数排序，其时间复杂度为O(d*n)。 （3）两种基本操作 ①比较两个关键字的大小； ②将记录从一个位置移动至另一个位置。 前一种基本操作对大多数的排序方法是必须的，而后一个操作可以通过改变记录的存储方式来予以避免。 （4）存储方式 待排序的记录序列可有下列3中存储方式： ①待排序的一组记录存放在地址连续的一组存储单元上。 ②一组待排序记录存放在静态链表中。在此方式下实现的排序又称 （链）表排序。 ③待排序记录本身存储在一组地址连续的存储单元内，同时另设一 个指示各个记录存储位置的地址向量。在此方式下实现的排序又 称地址排序。 排序的方法有很多，但简单地判断那一种算法最好，以便能够普遍选用则是困难的。 评价排序算法好坏的标准主要有两条：算法执行所需要的时间和所需要的附加空间。 另外，算法本身的复杂程度也是需要考虑的一个因素。 排序算法所需要的附加空间一般都不大，矛盾并不突出。而排序是一种经常执行的一 种运算，往往属于系统的核心部分，因此排序的时间开销是算法好坏的最重要的标志。 （5）数据类型 待排记录的数据类型设为： #define MAXSIZE 20 //一个用作示例的小顺序表的最大长度 typedef int KeyType; //定义关键字类型为整数类型 typedef struct { KeyType key; //关键字项 InfoType otherinfo; //其他数据项 } RedType; //记录类型 typedef struct { RedType