第九章排序(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个待排序的元素看成为一个有序表和一个无序 表 依次将各个数据插入已排序好的有序子表中