数据结构讲义 第10章 内部排序- 插入排序.pdf

数据结构讲义 第10章 内部排序 第10章 内部排序 - 插入排序 数据结构课程的内容 数据结构课程的内容 10.1 概述 10.1 概述 1. 什么是排序？ 将一组杂乱无章的数据按一定的规律顺次排列起来。 定义：设有记录序列： {R1、R2 … Rn} 其相应的关键字序列为： {K1、K2 … Kn}; 若存在一种确定的关系： Kx=Ky …=Kz， 将记录序列 {R1、R2 … Rn} 排成按该关键字有序 的序列： {Rx、Ry … Rz}， 这样的操作称之为排序。 2. 排序的目的是什么？ ——便于查找！ 3.排序算法的好坏如何衡量？ • 时间效率——排序速度 • 空间效率—— 占内存辅助空间的大小 • 稳定性——若两个记录A和B的关键字值相等，但排 序后A、B的先后次序保持不变，则称这种排序算法 是稳定的。 4. 什么叫内部排序？什么叫外部排序？ 4. 什么叫内部排序？什么叫外部排序？ ——若待排序记录都在内存中，称为内部排序； ——若待排序记录一部分在内存，一部分在外存，则 称为外部排序。 5. 内部排序的算法有哪些？ 5. 内部排序的算法有哪些？ ——按排序的规则不同，可分为5类： • 插入排序（希尔排序） • 交换排序（快速排序） • 选择排序（堆排序） • 归并排序 • 基数排序 ——按排序算法的时间复杂度不同，可分为3类： •简单的排序算法：时间效率低，O(n2) •先进的排序算法: 时间效率高，O( nlog2n ) •基数排序算算法：时间效率高，O( d ×n) 大多数排序算法都有两个基本的操作： （1）比较两个关键字的大小 （2 ）将记录从一个位置移动到另一个位置 记录序列的存储方式： （1）顺序存储 （2 ）静态链表 （3 ）地址 6. 顺序存储（顺序表）的抽象数据类型如何表示？ 6. 顺序存储（顺序表）的抽象数据类型如何表示？ 注：大多数排序算法都是针对顺序表结构的(便于直接移动元素) # define MAXSIZE 20 //设记录不超过20个 typedef int KeyType ; //设关键字为整型量（int型） Typedef struct { //定义每个记录（数据元素）的结构 KeyType key ; //关键字 InfoType otherinfo; //其它数据项 }RecordType ; Typedef struct { //定义顺序表的结构 RecordType r [ MAXSIZE +1 ]; //存储顺序表的向量 //r[0]一般作哨兵或缓冲区 int length ; //顺序表的长度 }SqList ; 10.2 插入排序 10.2 插入排序 每步将一个待排序的对象， 插入排序的基本思想是：每步将一个待排序的对象， 插入排序的基本思想是： 按其关键码大小，插入到前面 已经排好序的一组对象 按其关键码大小，插入到前面 已经排好序的一组对象 的适当位置上，直到对象全部插入为止。 的适当位置上，直到对象全部插入为止。 简言之，边插入边排序，保证子序列中随时都是排好序的。 简言之，边插入边排序，保证子序列中随时都是排好序的。 插入排序有多种具体实现算法：