数据结构之排序课件.ppt

数据结构 第九章 排序 第九章 排序 知 识 点 排序的基本概念 三种简单的排序方法：冒泡排序、直接选择排序、简单插入排序 堆排序 快速排序 归并排序 基数排序 难 点 堆排序 快速排序 归并排序 基数排序 要 求 熟练掌握以下内容： 熟悉各种内部排序方法的基本思想和特点 各种排序方法的优缺点、时、空性能和适用场合 熟悉并掌握三种简单排序算法、快速排序算法和堆排序算法 了解以下内容： 二路归并排序算法 基数排序算法 排序的历史 大约公元前300年，在爱琴岛上发现了若干个表, 给出了宗教中的人名.这些表按字母排列,但只按头一个字母排列.(单个字母的字符排序) 约公元前200年, 巴比伦人艾娜基比特-安奴(Inakibit-Anu),用陶土做的,含有500个以上高精度的六十进制数及其倒数表,并把它排列成词典顺序.(数字排序) 在许多圣经赞美诗中,遵循一个严格的字母序列,头一个诗句以a开始,第二个诗句以b开始,……有助于记忆.(单个字母的字符排序) 公元134-135年,某些希腊文稿包含一些分类账的片断,他列出了按头两个字母排序的纳税人的名字. …… 对于今天排序技术起源的探索,是19世纪末发明的排序机器.1880年,美国人口普查,数据处理成为令人头痛的问题—无法在当年完成. 赫尔曼.霍勒里斯(Herman Hollerith),一位人口统计局的20岁的职员,发明了一台巧妙的制表机,用100台这样的制表机,成功的完成了人口普查的统计问题. …… 计算机的诞生和发展促进了排序技术的发展 1945年,冯.诺依曼(Von Neuman)编制了一个用于内部合并排序的程序---这也是存储程序计算机的第一个程序. …… 如果我能把过去几年内所产生的大量的关于排序的材料的要旨都加以排序,编排出次序来,那我就心满意足了. ----J.C.霍斯金(J.C.Heskin 1955) 9.1 排序的概念 将一组杂乱无序的数据按一定的规律顺次排列起来叫做排序(sort)。 关键字(key)：对一批记录的排序，应该指定是根据记录中哪个字段进行排列。这个作为排序依据的字段称之为关键字。 约定：本章讨论的排序均为按递增顺序排序，并假定要排序的记录均已存储在一个一维数组中。 记录的形式定义为： Typedef struct rectype { KeyType key; /*关键字*/ itemType otherinfo; /*其他域*/ }rectype; 大多数的排序方法数据是存储在内存中，并在内存中加以处理的，这种排序方法叫内部排序。 如果在排序过程中，数据的主要部分存放在外存储器中（如软盘、硬盘、磁带），借助内存进行内、外存数据交换，逐步排列记录之间的顺序，则称之为外部排序。 一种排序方法，如果排序后具有相同关键字的记录仍维持排序之前的相对次序，则称之为稳定的，否则称为不稳定的。 9.2 三种简单排序算法 1 直接插入排序 基本思想：设有n个待排序的记录，顺序存放在数组R[1—n]中。设前I-1个记录已经有序，从第I个记录开始和前I-1个记录的关键字比较，找到合适的位置插入。 直接插入算法需要经过（n-1）趟插入过程。如果数据恰好应插入到序列的最后端，则不需移动数据，可节省时间，所以若原始数据大体有序，此算法可以有较快的运算速度。 图9.1 直接插入排序 直接插入排序算法 void insertsort (rectype r[], int n) { int i,j; for( i=2; i=n; i++) { r[0]=r[i]; /* r[0]用于暂时存放待插入的元素*/ j= i-1; /* j为待比较元素下标 while (r[0].keyr[j].key) { r[j+1]=r[j]; /*记录后移*/ j--; } r[j+1]=r[0]; /* 在j+1位置插入r[0]*/ } } 性能分析 最好的情况：当待排序的记录已经有序时，比较次数为 n-1；移动次数为2（n-1） 最坏的情况：当待排序的记录按递减排列时，比较次数为 2+3+……+n=(n-1)(n+2)/2 移动次数为?(I+1)=(n-1)(n+4)/2 取其平均值：比较次数和移动次数