《数据结构》课程教学资源（PPT课件讲稿）第九章 排序 Sort

第九章排序(Sort) 2007.9

第九章 排序 (Sort) 2007.9

主要内容 91排序的基本概念 92插入排序 93交换排序 94选择排序 95各种排序方法的比较 排序( Sorting)是数据处理中一种很重要的运算 同时也是很常用的运算,一般数据处理工作25%的 时间都在进行排序

主要内容 9.1 排序的基本概念 9.2 插入排序 9.3 交换排序 9.4 选择排序 9.5 各种排序方法的比较 排序（Sorting）是数据处理中一种很重要的运算， 同时也是很常用的运算，一般数据处理工作25%的 时间都在进行排序

91排序的基本概念

9.1 排序的基本概念

排序的对象:表 由一组记录组成的文件 排序的依据:关键字(key) 关键字(key),记录中的一个属性,是任何一种可比的有 序数据类型 排序的顺序: 升序/降序 排序定义: 将一组记录按某关键字递增或递减排列的过程。 内部排序与外部排序 文件是否整个存放于内存,排序时是否需要涉及内、外 存的数据交换

 排序的对象：表  由一组记录组成的文件。  排序的依据：关键字（key）  关键字（key）,记录中的一个属性, 是任何一种可比的有 序数据类型  排序的顺序：  升序/降序  排序定义：  将一组记录按某关键字递增或递减排列的过程。  内部排序与外部排序：  文件是否整个存放于内存，排序时是否需要涉及内、外 存的数据交换

算法的性能评价 时间复杂度 比较次数、移动次数、数据规模、数据的初 始状态 空间复杂度 辅助空间 稳定性 对于具有同一排序关键字的多个记录,若排序后,记 录的相对次序不变,则称此排序方法是稳定的,否则 称为不稳定的。 算法的复杂度

算法的性能评价  时间复杂度：  比较次数、移动次数、数据规模、数据的初 始状态  空间复杂度：  辅助空间  稳定性  对于具有同一排序关键字的多个记录，若排序后，记 录的相对次序不变，则称此排序方法是稳定的，否则 称为不稳定的。  算法的复杂度

typedef struct i 表的存储结构 char i no char name, ●数组 int mark1 typedef struct i int mark2 int ke int aver; datatype other student rectype R student class[501 链表 学号姓名年龄性别 索引表 学 99001王晓佳18 生9902林一鹏19 档 99003谢宁17 案 表 99004张丽娟18 99005周涛 男男女女男女 99006李小燕16

表的存储结构  数组 typedef struct { int key; datatype other; } rectype R[N];  链表  索引表 typedef struct { char * no; char * name; int mark1; int mark2; int aver; } student; student class[50]; 学 生 档 案 表 学号 姓名 年龄 性别 99001 王晓佳 18 男 99002 林一鹏 19 男 99003 谢宁 17 女 99004 张丽娟 18 女 99005 周涛 20 男 99006 李小燕 16 女

基本的内部排序方法 ●插入( Insert) 直接插入( Straight Insertion Sort) 希尔排序( Shell sort 交换(Swap) 冒泡排序( Bubble sort) 快速排序( Quick Sort ●选择( Select) 直接选择( Straight Selection Sort) 堆排序( Heap Sort) 归并( Merge Sort)

基本的内部排序方法  插入 （ Insert ）  直接插入（Straight Insertion Sort）  希尔排序（Shell Sort）  交换（Swap）  冒泡排序 （Bubble Sort）  快速排序（Quick Sort）  选择 （Select）  直接选择 （ Straight Selection Sort）  堆排序（Heap Sort）  归并（Merge Sort ）

92插入排序

9.2 插入排序

92插入排序 nsertion Sorting) ●基本思想: 依次将无序表中的记录插入有序表的适当位置。 基本算法 直接插入排序( Straight Insertion sort) 希尔排序( Shell sort)

9.2 插入排序Insertion Sorting）  基本思想：  依次将无序表中的记录插入有序表的适当位置。  基本算法  直接插入排序（ Straight Insertion sort）  希尔排序 （Shell sort）

921直接插入排序 1.直接插入排序的基本思想 n个待排序的元素看成为一个有序表和一个无序 表 ●依次将各个数据插入已排序好的有序子表中

9.2.1 直接插入排序 1．直接插入排序的基本思想  n个待排序的元素看成为一个有序表和一个无序 表  依次将各个数据插入已排序好的有序子表中