数据结构ch08.doc

第 8 章 排序技术 8.1 概 述 8.1.1 排序的基本概念 在排序问题中，通常将数据元素称为记录。 排序 简言之，排序是将一个记录的任意序列重新排列成一个按关键码有序的序列。严格地说，给定一个记录序列(r1，r2，…，rn)，其相应的关键码分别为(k1，k2，…，kn)，排序是将这些记录排列成顺序为(rs1，rs2，…，rsn)的一个序列，使得相应的关键码满足ks1≤ks2≤…≤ksn（升序）或ks1≥ks2≥…≥ksn（降序）。 正序、逆序 若待排序序列中的记录已按关键码排好序，称此记录序列为正序； 若待排序序列中记录的排列顺序与排好序的顺序正好相反，称此记录序列为逆序或反序。 趟 在排序过程中，将待排序的记录序列扫描一遍称为一趟。 排序算法的稳定性 假定在待排序的记录序列中，存在多个具有相同关键码的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ki=kj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法稳定；否则称为不稳定。 单键排序、多键排序 根据一个关键码进行的排序称为单键排序； 根据多个关键码进行的排序称为多键排序，这主要针对关键码有重复的情况。 多键排序可以转化成单键排序。 排序的分类 ·排序方法分为内排序和外排序两大类。 内排序： 外排序： ·根据排序方法是否建立在关键码比较的基础，将排序方法分为 基于比较的排序： 不基于比较的排序： ·根据排序过程中依据的原则对基于比较的内排序进行分类，大致可分为插入排序、交换排序、选择排序、归并排序等四类。 8.1.2 排序算法的性能 对于基于比较的内排序，在排序过程中通常需要进行下列两种基本操作：⑴ 比较：关键码之间的比较；⑵ 移动：记录从一个位置移动到另一个位置。 评价排序算法的另一个主要标准是执行算法所需要的辅助存储空间。 另外，算法本身的复杂程度也是一个要考虑的因素。 8.2 插入排序 8.2.1 直接插入排序 直接插入排序的基本思想是：依次将待排序序列中的每一个记录插入到一个已排好序的序列中，直到全部记录都排好序。 问题⑴的解决： 问题⑵的解决： 8.2.2 希尔排序 希尔排序的基本思想是：先将整个待排序记录序列分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。 问题⑴的解决： 问题⑵的解决： 8.3 交换排序 8.3.1 起泡排序 起泡排序的基本思想是：两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。 问题⑴的解决： 问题⑵的解决： 问题⑶的解决： 8.3.2 快速排序 快速排序又称为分区交换排序，其基本思想是：首先选一个轴值（即比较的基准），将待排序记录分割成独立的两部分，左侧记录的关键码均小于或等于轴值，右侧记录的关键码均大于或等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。 问题⑴的解决： 问题⑵的解决：设待排序序列是r[s] ~ r[t]，一次划分的过程用伪代码描述为： 具体的一次划分算法如下： 问题⑶和⑷的解决： 8.4 选择排序 8.4.1 简单选择排序 简单选择排序是选择排序中最简单的排序方法，其基本思想是：第i趟排序通过n-i次关键码的比较，在n-i+1（1≤i≤n-1）个记录中选取关键码最小的记录，并和第i个记录交换作为有序序列的第i个记录。 问题⑴的解决： 问题⑵的解决： 8.4.2 堆排序 1. 堆的定义 堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（小根堆）；或者每个结点的值都大于或等于其左右孩子结点的值（大根堆）。 如果将堆按层序从1开始编号，则结点之间满足如下关系 堆调整的问题：在一棵完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？ 假设当前要筛选结点的编号为k，堆中最后一个结点的编号为m，并且结点k的左右子树均是堆（即r[k+1] ~ r[m]满足堆的条件），则筛选算法用伪代码可描述为： 筛选算法如下： 2. 堆排序 堆排序的基本思想是：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录为止。 问题⑴的解决： 问题⑵的解决： 问题⑶的解决： 8.5 归并排序 8.5.1 二路归并排序的非递归实现 问题⑴的解决： 问题⑵的解决： 问题⑶的解决： 若i≤n-2h+1，则 若i＜n-h+1，则 ③ 若i≥n-h+1，则 问题⑷的解决： 8.5.2 二路归并排序的递归实现 8.6 各种排序方法的比