数据结构排序详解.ppt

第 十 章 排 序 10.1 概 述 10.1 概 述 10.1 概 述 10.1 概 述 按排序所需工作量 简单的排序方法：T(n)=O(n2) 先进的排序方法：T(n)=O(n*logn) 基数排序：T(n)=O(d*n) 排序基本操作 比较两个关键字大小 将记录从一个位置移动到另一个位置 10.1 概 述 10.1 概 述 10.1 概 述 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 2. 折半插入排序 排序过程：用折半查找方法确定插入位置的排序叫~ 10.2 插入排序 算法描述 10.2 插入排序 10.3 交换排序 10.3 交换排序 10.3 交换排序 10.3 交换排序 10.3 交换排序 10.4 选择排序 10.4 选择排序 10. 5 归并排序 结束 第 * 页 * 第十章 排 序 10.1 概述 10.2 插入排序 10.3 交换排序 10.4 选择排序 10.5 归并排序  学习要点 理解排序的定义和各种排序方法的特点； 了解各种方法的排序过程及其依据的原则； 理解“稳定”或“不稳定”的含义； 1 排序定义 将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫排序。 假设含n个记录的序列为：{ R1 R2 R3 … Rn } 其相应的关键字为： {K1,K2, K3 … Kn} 需确定1，2，…，n的一种排列p1,p2,…,pn，使其相应的关键字满足如下的非递减（或非递增）关系 Kp1= Kp2 = … = Kpn 即使（10-1）的序列成为一个按关键字有序的序列 {Rp1，Rp2，…，Rpn} 这样一种操作称为排序。 2 稳性排序： 在待排记录序列中，任何两个关键字相同的记录，用某种排序方法排序后相对位置不变，则称这种排序方法是稳定的，否则称为不稳定的。 例 设 49,38,65,97,76,13,27,49 是待排序列 排序后:13,27,38,49,49,65,76,97 —— 稳定 排序后:13,27,38,49,49,65,76,97——不稳定 3 分类 按记录的存放位置分类有 内排序：待排记录放在内存 外排序：待排记录放在外存 ·按排序原则分类（内排序） 插入排序 交换排序 选择排序 归并排序 基数排序 4 存储方式待排序的记录序列通常有下列三种存储方法：1）顺序表2）静态链表：在排序过程，只需修改指针，不需要移动记录(表排序)；3）待排记录本身有放在连续单元中，同时另建一索引表——用于存放各记录存贮位置；排序时不移过记录本身，而移动索引表中的记录“地址”，在排序结束后再按地址调整记录的存贮位置（地址排序）。 5 约定 在本章中 1)为简洁起见，对待排记录只写出其关键字序列 如对待排记录（(09,10),(06,10.5),(033,9.8),(051,10)) 只写出其关键字序列（10，10.5，9.8，10） 2）将按关键字递增的顺序排序 3)待排序记录用顺序表存储，且关键字均为整数 顺序表类型说明 #define MAXSIZE 20 //一个用作示例的小顺序表的最大长度 typedef int KeyType; //定义关键字类型为整数类型 typedef struct{ KeyType key; //关键字项 InfoType otherinfo; //其它数据项 }RedType; //记录类型 typedef struct{ RedType r[MAXSIZE+1]; //r[0]闲置或用作哨兵单元 Int length; //顺序表长度 }SqList; //顺序表类型 1、直接插入排序 基本思想 将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。 排序过程： 整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。 例 49 38 6