《数据结构与程序设计 第九章 排序》由会员分享，可在线阅读，更多相关《数据结构与程序设计 第九章 排序（89页珍藏版）》请在金锄头文库上搜索。
1、第九章 排序内容提要： u五类内部排序方法（插入排序、交换排序 、选择排序、归并排序和基数排序）的基本 思想、排序过程、实现的算法、算法的效率 分析及排序的特点； u各种排序方法的比较和选择； u最后简单介绍外部排序。1排序的功能是将一个数据元素(记录)的任 意序列，重新排列成一个按关键字有序的 序列，目的是为了便于查询和处理数据。 排序的定义2排序的分类l按待排序记录所在位置 内部排序：待排序记录存放在内存 外部排序：排序过程中需对外存进行访问 的排序l按排序依据原则 插入排序：直接插入排序、折半插入排序 、希尔排序 交换排序：冒泡排序、快速排序 选择排序：简单选择排序、堆排序 归并排序：2
2、-路归并排序3排序的基本操作l比较两个关键字大小l将记录从一个位置移动到另一个位置4排序的性质如果在待排序的数据中，存在多个 关键字相同的数据，经排序后这些数 据的相对次序仍然保持不变，则称相 应的排序方法为稳定方法，否则为不 稳定方法。5定义待排序的记录的数据类型为：#define recnum 100 struct rectype int key; int item; ;struct rectype arecnum+1;排序对象的数据类型6基本思想：每步将一个待排序的记录，按其 关键字值的大小插入到前面已经排序的文件 中适当的位置上，直到全部插完为止。插入排序7基本思路是依次把待排序的记录
3、逐一按其关 键字的大小插入到一个已经排好序的有序序 列中去，直到所有的记录插完为止。得到一 个新的有序序列。插入排序直接插入排序8例49 38 65 97 76 13 27i=2 38 (38 49) 65 97 76 13 27i=3 65 (38 49 65) 97 76 13 27i=4 97 (38 49 65 97) 76 13 27i=5 76 (38 49 65 76 97) 13 27i=6 13 (13 38 49 65 76 97) 27i=1 ( )i=7 (13 38 49 65 76 97) 2727jjjjjj977665493827(13 27 38 49 65
4、76 97)排序结果：比较次数 移动次数1 11 02 1.1 05 56 5插入排序直接插入排序9（1）设置监视哨 a0，将待插入记录的 值赋给a0; （2）设置开始查找的位置j； （3）在数组中进行搜索，搜索中将第j个 记录后移，直至a0.keyaj.key为止 （4）将a0插入在aj+1的位置上直接插入排序算法10void straipass(a, i) struct rectype arecnum+1; int i; int j, x;a0=ai;j=i-1;x=ai.key;11while(x=j+1;k-)ak+1=ak; Aj+1=a0; 19void binsort(a,j)s
5、truct rectype arecnum+1;int j; int i;for(i=2;i=0 iaj+1.key)temp=aj;aj=aj+1;aj+1=temp; 34改进算法mark=i; while(mark) m=mark-1;mark=0;for(j=1;jaj+1.key)temp=aj; aj=aj+1; aj+1=temp;mark=j; 35由上述算法可见，当初始序列中记录已 按关键字次序排好序，则只需要进行一 趟排序，在排序过程中只需要进行n-1 次比较，记录移动次数为0；反之，若 初始序列中记录按逆序排列，若待排序 的序列有n个记录，最多进行n-1趟排序 ，最大比较
6、次数为冒泡排序算法分析36冒泡排序交换记录时移动记录的次 数也约为3n2 /2次，故总的时间复杂 度为O(n2 )。冒泡排序是稳定的。37交换排序快速排序基本思想：通过一趟排序，将待排序记录分割成 独立的两部分，其中一部分记录的关键字均比另 一部分记录的关键字小，则可分别对这两部分记 录进行排序，以达到整个序列有序38对rst中记录进行一趟快速排序，附设两 个指针i和j，设枢轴记录rp=rs，x=rp.key u初始时令i=s,j=t u首先从j所指位置向前搜索第一个关键 字小于x的记录，并和rp交换 u再从i所指位置起向后搜索，找到第一 个关键字大于x的记录，和rp交换 u重复上述两步，直至
7、i=j为止 u再分别对两个子序列进行快速排序， 直到每个子序列只含有一个记录为止快速排序的排序过程39例初始关键字： 49 38 65 97 76 13 27 50 ijxji完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分别进行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序结束： 13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij快速排序的排序过程401）确定第一个记录为基准记录rt，先从j所指示的位 置起向前扫描，当rt.keyrj.key时，交换rt.key 和rj.k
8、ey，使关键字值比基准记录的关键字值小的 记录交换到前面； 2）从i所指示的位置起向后扫描，直到rt.keyri.key, 交换rt.key和ri.key，使关键字值比基准记录的关 键字值大的记录交换到后面； 3）重复（1）和（2），直至i=j为止完成一趟排序； 4）只要tw，重复（1）至（3）分别对基准记录两边 的部分进行排序。快速排序的排序算法41快速排序平均时间复杂度为O(nlog2 n)。最坏情况下时间复杂度为O(n2)，快速排序所 需的比较次数反而最多。快速排序法不稳定。快速排序需要一个栈空间来实现递归。栈的 最大深度为 log2 n 1，所需栈空间为 O(log2 n)。最坏情况下
9、，递归深度为n，所需 栈空间为O(n)。快速排序的排序算法分析42选择排序选择排序是指每次从待排序的记录中 选出关键字值最小（或最大）的记录，顺 序放在已排序的有序序列中，直到全部排 完。选择排序主要包括简单选择排序和堆 排序两种。43选择排序简单选择排序u首先通过n-1次关键字比较，从 n个记录中找出关键字最小的记录 ，将它与第一个记录交换 u再通过n-2次比较，从剩余的n- 1个记录中找出关键字次小的记录 ，将它与第二个记录交换 u重复上述操作，共进行n-1趟排 序后，排序结束44例初始： 49 38 65 97 76 13 27 kjjjjjjkki=11349一趟： 13 38 65
10、97 76 49 27 i=2kkjjjjj2738二趟： 13 27 65 97 76 49 38 三趟： 13 27 38 97 76 49 65 四趟： 13 27 38 49 76 97 65 五趟： 13 27 38 49 65 97 76 六趟： 13 27 38 49 65 76 97 排序结束： 13 27 38 49 65 76 97 45(1)查找待排序序列中最小的记录，并将它 和该区间第一个记录交换；(2)重复（1）到第n-1次排序后结束简单选择排序算法46简单选择排序所需要的总的比较次 数为O(n2 )。当初始文件是有序时，最 小移动记录次数等于0，而当初始文件 是逆序
11、时，每次都要交换记录 。直接选择排序是不稳定的.简单选择排序算法分析47选择排序堆排序的引入堆排序是简单选择排序的改进。用直接 选择排序从n个记录中选出关键字值最小的 记录要做n-1次比较，然后从其余n-1个记录 中选出最小者要作n-2次比较。显然，相邻 两趟中某些比较是重复的。为了避免重复比 较，可以采用树形选择排序比较。 48(a)求出最小关键字3 (b) 求出次小关键字11 图 8.8 树形选择排序49树形选择排序总的比较次数为O(nlog2 n) ，与直接选择排序比较，减少了比较次数 ，但需要增加额外的存储空间存放中间比 较结果和排序结果。选择排序堆排序的引入50n个元素的序列(k1,
12、k2,kn)，当且仅当满足 下列关系时，称之为堆或(i=1,2,.n/2)kik2i kik2i+1kik2i kik2i+1例 （96，83，27，38，11，9）例 （13，38，27，50，76，65，49，97）962791138831327384965765097可将堆序列看成完全二叉树，则堆顶 元素（完全二叉树的根）必为序列中 n个元素的最小值或最大值堆的定义51堆排序的基本思路：对一组待排序的记 录序列，先将其关键字按堆的定义排列个 序列（称初建堆），找到了最小（最大）关 键字，将其取出。用剩余的n-1个元素再重建 堆，便可得到次小（次大）值。如此反复执 行，直到全部关键字排好序
13、为止。 堆排序的基本思路52例13273849657650979727384965765013输出：132749389765765013输出：139749382765765013输出：13 273849502765769713输出：13 276549502738769713输出：13 27 38534965502738769713输出：13 27 387665502738499713输出：13 27 38 495065762738499713输出：13 27 38 499765762738495013输出：13 27 38 49 506597762738495013输出：13 27 38 49
14、 509765762738495013输出：13 27 38 49 50 65547665972738495013输出：13 27 38 49 50 659765762738495013输出：13 27 38 49 50 65 769765762738495013输出：13 27 38 49 50 65 76 9755堆排序的关键问题堆排序需解决的两个问题： u如何由一个无序序列建成一个堆 ？ u如何在输出堆顶元素之后，调整 剩余元素，使之成为一个新的堆 ？56堆排序的关键问题l第二个问题解决方法筛选 方法：输出堆顶元素之后，以堆中最后一个元素 替代之；然后将根结点值与左、右子树的根结点 值进
15、行比较，并与其中小者进行交换；重复上述 操作，直至叶子结点，将得到新的堆，称这个从 堆顶至叶子的调整过程为“筛选”。l第一个问题解决方法建堆 方法：从无序序列的第n/2个元素（即此无序序 列对应的完全二叉树的最后一个非终端结点）起 ，至第一个元素止，进行反复筛选。57例：含8个元素的无序序列（49，38，65，97，76，13 ，27，50），建堆过程：49653827137697504965382713765097491338276576509749133827657650971327384965765097 58堆排序只需要一个记录大小的辅助空间。 堆排序算法的时间复杂度为O(nlogn)。 堆排序是一种不稳定的排序方法。堆排序的算法及分析59归并排序归并排序：把两个或多个有序表进行合 并，得到一个
