数据结构——排序.ppt(492.5KB).ppt

山东大学管理学院 戚桂杰 数据结构 山东大学管理学院 * 山东大学管理学院 戚桂杰 * 本章主要内容 （1）排序的基本概念 （2）内排序：插入排序、交换排序、堆排序、 归并排序 （3）外排序简介 * 山东大学管理学院 戚桂杰 * §1 概述 排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。 假设含n个记录的序列为 {R1，R2，…，Rn} (7-1) 其相应的关键字序列为 {K1，K2，…，Kn} 需确定1,2, …,n的一种排列p1,p2, …,pn ,使其相应的关键字满足如下的非递减（或非递增）关系 KP1 ≤ KP2 ≤ … ≤ KPn (7-2) 即使(7-1)的序列成为一个关键字有序的序列 {RP1 ，R P2 ， … ，R Pn } (7-3) 这样一种操作称为排序。 * 山东大学管理学院 戚桂杰 * §1 概述 稳定的排序方法 不稳定的排序方法 由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类： 一类是内部排序，指待排序记录放在计算机随机存储器中进行的排序过程； 另一类是外部排序，指在排序过程中需对外存访问的排序过程。 按在排序过程中依据的不同原则，内部排序可以分为插入排序、交换排序、选择排序、归并排序和基数排序五类。 按在内部排序过程中需要的工作量可以分为：(1)简单的排序方法时间复杂度为O(n2)； (2)先进的排序方法，时间复杂度为O(nlogn)；(3)基数排序，时间复杂度O(d·n) * 山东大学管理学院 戚桂杰 * §1 概述 在排序的过程中需进行两种基本操作：(1)比较两个关键字的大小；(2)将记录从一个位置移动至另一个位置。 待排序的记录序列可有三种存储方式：（1）顺序存储方式；（2）链接存储方式；（3）顺序存储方式+地址向量 * 山东大学管理学院 戚桂杰 * §2 插入排序 直接插入排序 它是由n-1趟排序组成的。例如，在第i趟排序前（2≤i≤n），位置从1到i-1上的记录是已排过序的，则第i趟排序是向第1到i-1个有序记录之间插入一个新记录，使插入后的记录序列仍为有序，排序过程的每一步类似于线性表中有序表的插入。 如图7-1显示了一个数组在每一趟插入排序后的情况变化： 初始 (44) 18 74 61 42 31 插入元素 i=2趟排序后 (18 44) 74 61 42 31 18 i=3趟排序后 (18 44 74) 61 42 31 74 i=4趟排序后 (18 44 61 74) 42 31 61 i=5趟排序后 (18 42 44 61 74) 31 42 i=6趟排序后 (18 31 42 44 61 74) 31 图7.1 插入排序示例 * 山东大学管理学院 戚桂杰 * void InsertSort(ElemType P[ ], int n){ //对具有n个记录的数组P作直接插入排序 //n个记录存放在数组P[1..n]中，P[0]留作“哨兵”使用 for(i=2; i=n; i++) if(P[i].keyP[i-1].key){ //将P[i]插入有序子表 P[0]=P[i]; P[i]=P[i-1]; for(j=i-2; P[0].keyP[j].key; j--) P[j+1]=P[j]; //向后移动数组记录 P[j+1]=P[0]; //插入记录 } }//InsertSort 算法7-1 直接插入排序 插入排序的时间复杂度为O(n2)。该算法在n较小时或待排序的记录基本有序时还是较为适用的。 * 山东大学管理学院 戚桂杰 * 改进的插入排序方法——折半插入排序 void BiInsertSort(ElemType P[ ], int n){ //对具有n个记录的数组P作折半插入排序 //n个记录存放在数组P[1..n]中 for(i=2; i=n; i++){ P[0]=P[i]; //P[0]作为辅助空间 low=1; hi