《数据结构与算法c（5）》由会员分享，可在线阅读，更多相关《数据结构与算法c（5）（68页珍藏版）》请在金锄头文库上搜索。
1、11.5.3 二路归并排序,11.5.2 多段2路合并,11.5.1 二路合并,11.4.2 堆排序,11.4.1 直接选择排序,11.3.2 冒泡算法的改进,11.3.3 快速排序*,11.3.1 冒泡排序,11.2.2其他插入排序算法,11.2.1 直接插入排序,11.6 外排排简介,11.5归并排序,11.4 选择排序,11.3 交换排序,11.2 插入排序,11.1 概述,第 11 章 排序算法,从操作角度看，排序是线性结构的一种操作，在当今的计算机系统中，花费在排序上的时间占系统CPU运行时间的比重很大。有资料表明，在一些商用计算机上，用在排序上的CPU时间达到20%至60%。为了提
2、高排序效率，人们已对排序进行了许多研究，提出了许多方法/算法。从算法设计角度看。排序算法不仅对排序本身重要，而且展示了算法设计的某些重要原则和高超的技巧，所以也是重要的算法设计方法。因此，对于计算机专业人员来说，认真研究和掌握排序算法是十分重要的。,11.1 概述,排序（Sorting）（也称整序）通常被理解为按规定的原则重新安排一组给定的对象的的排列次序。排序的主要目的是便于以后在已排序的集合中查找/检索某一成员。日常生活中，通过排序以便于检索的例子屡见不鲜。例如，电话号码簿、目录表、图书馆、词典、仓库以及一切需对所存贮的对象进行检索的地方都要先将对象加以排序。下面先介绍若干概念。,1关键字
3、：关键字形式上是记录中的某个字段（或某些字段的组合），在具体的操作中，用于代表其所在的记录。对排序操作，是以关键字字段的内容的大小进行排序的。记录中关键字字段的值称为键值。键值一般为数值或字符串。 2排序：在数据结构中，排序被认为是定义在数据集合上的一种运算，其功能是将一组任意排列的数据元素（在排序中称为记录）重新排列成一个按键值有序的序列。具体地，排序定义如下定义： 设R1，R2，Rn为含n个记录的序列，其相应的键值序列为k1，k2，kn。排序是将这些记录重新排列为Ri1，Ri2，Rin，使得相应的键值满足条件ki1ki2kin（升序），或满足ki1ki2kin（降序）。这里的比较运算（或）
4、，或是数值比较，或是字符串比较。 3排序的稳定性：假定在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变（即在原序列中ki=kj，ij；而在排序后的序列中，Ri 仍在Rj之前），则称这种排序方法是稳定的，否则称为不稳定的。,4内排序：由于记录的形式、数量和所存放的存储设备不同，排序所采用的方法也不同。按照排序过程涉及的存储设备的不同，排序分为内排序（internal sorting）和外排序（external sorting）两大类。内排序是指在排序的整个过程中，数据全部存放在计算机的内存中，排序所需所有操作只需在内存中进行，不需进行内外存交换。内排序适
5、用于记录个数不太多的小文件，同时也是外排序的基础。 5外排序：是指在排序过程中，待排序的数据较多，不能一次全部装入内存继续排序，需进行内外存交换（即读入部分数据，处理后写回外存，然后再读入其他部分）。外排序适用于记录个数很多，不能一次将其全部都放入内存的大文件。 本章先集中讨论内排序的各种典型方法和算法，最后再简单介绍一下外排序。 6多键排序：按多个关键字排序。这主要针对关键字值有重复的情况。首先按第一关键字排序，对第一关键字相等的记录，按第二关键字排序，而第二关键字也相等的记录再按第三关键字排，余类推。 多键排序有两种方式（设第1到第n个关键字分别为k1, k2, , kn）： a) 依次对
6、记录进行n次排序，第一次按kn排序，第二次按kn-1，, 最后一次按k1排。这种方法要求各趟排序所用算法是稳定的。 b) 先将关键字k1, k2, , kn分别视为字符串，将它们依次首尾连接在一起，形成一个字符串，然后，对记录集按新形成的字符串排序。 不论那种无法，多键排序都被转化为了单键排序，所以，我们只讨论单键排序的情况。 显然，方法b)的速度要快于a).,内排序的方法很多，如果按排序过程中依据的不同原则对内排序方法进行分类，则主要分为为：插入排序、交换排序、选择排序、归并排序等四类，另一类是分配排序。 为了比较各种排序算法的优劣，要分析算法的时间复杂性。为此，通常只考虑键值的比较次数和记
7、录的移动次数，即以键值比较和记录移动为标准操作。当键值是字串的时候，比较要占用较多的时间，是影响时间复杂性的主要因素。而当记录很大时，为了交换记录的位置，移动记录也要占用较多的时间，是影响时间复杂性的另一个主要因素。评价排序的另一个主要标准是执行算法所需的附加空间。 排序一般在记录集上进行，也可以认为是在线性结构上进行。为了突出主题，我们不失一般性地假定，待排序的记录为一维数组a，数组的每个元素是整数。另外，如无特别说明，都假定是按升序排序。,11.2 插入排序,插入排序类似玩纸牌时整理手中纸牌的过程。插入排序的基本方法是：每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位
8、置，直到全部记录插入完毕为止。,11.2.1 直接插入排序,直接插入排序（straight insertion sort）是一种最简单的排序方法，它的基本思想是，将待排序的记录集分成两部分，第一部分已排好序，第二部分未排好序。排序中，每次都是从第二部分中取出一条记录，就将其插入到第一部分，并使其保持有序。初始时，任取一条记录作为第一部分（一条记录总是有序的）,而其他记录作为第二部分。显然，随着排序过程的进行，第一部分不断扩大，第二部分不断缩小。总有一次，第二部分变为空，则第一部分包含了所有的记录，并且是有序的。,图 111给出了一个插入排序执行过程的例子。 下面考虑插入排序的计算机程序实现。很
9、自然地，我们可以将插入排序粗略地描述为： SortInsertion(int a, long n) for (i=1; i=0 ,综合起来，就得到插入排序的程序： int SortInsertion(int a, long n) int x, i,j; for (i=1; i=0 ,如果为了提高while循环的循环控制条件的判别速度，可在while进行前，将当前待插入的元素ai放在a数组中的第一个元素位置（代替语句x=ai），这样，while控制条件中的“j=0”就不需要了，从而起到节省时间的作用。,初始键值序 46 58 15 45 90 18 10 62,i=2 46 58 15 45 9
10、0 18 10 62 i=3 15 46 58 45 90 18 10 62 i=4 15 45 46 58 90 18 10 62 i=5 15 45 46 58 90 18 10 62 i=6 15 18 45 46 58 90 10 62 i=7 10 15 18 45 46 58 90 62 i=8 10 15 18 45 46 58 62 90,图 111直接插入排序过程示例,显然，该算法是稳定的，且时间复杂性为O（n2）。从空间来看，它只需要一个记录的辅助空间。,11.2.2其他插入排序算法,除了直接插入排序外，还有其他形式的插入排序，如折半插入排序、表插入排序和希尔排序等。它们是
11、对直接插入排序的改进。改进的关键点是，如何尽快地找到插入位置。例如，折半插入排序是每次将当前待插入元素与第一部分的中点位置上的元素比较，这样当记录数目很多时，可大大减少为寻找插入点而进行的比较次数。,11.3 交换排序,这里的交换，就是根据记录集中两个记录键值的比较结果来对换这两个记录在序列中的位置。交换排序的特点是：将键值较大的记录向记录集的一端移动，键值较小的记录向另一端移动。,11.3.1 冒泡排序,一个最简单的交换排序方法是冒泡排序法（bubble sort），它和气泡从水中往上冒的情况有些类似。具体做法是：先将第1个记录的键值和第1个记录的键值进行比较，如a0a1，则将两个记录交换。
12、然后比较第2个和第3个记录的键值，依同样的方法处理，接着同法处理第3个和第4个记录，等等，直到第n-1个记录和第n个记录进行比较交换，这称为一趟冒泡。一趟冒泡后，键值最大的记录传到了第n个位置。然后，对前n-1个记录进行同样操作，则具有第二大键值的记录被安置在第n-1个位置上。重复以上过程，每趟负责排好一个记录，经n-1趟后n个记录中有n-1个记录被排好，相当于全部n个记录排好。,例如，设初始记录集为 20 30 10 45 25 22 55 50 则第一趟冒泡的过程为： 20 30 10 45 25 22 55 50 /20与30比较，未交换 20 10 30 45 25 22 55 50
13、/30与10比较，交换 20 10 30 45 25 22 55 50 /30与45比较，未交换 20 10 30 25 45 22 55 50 /45与25比较，交换 20 10 30 25 22 45 55 50 /45与22比较，交换 20 10 30 25 22 45 55 50 /45与55比较，未交换 20 10 30 25 22 45 50 55 /55与50比较，交换,这样，最大数55被交换到了最后。接下来，进行其他(n-2)趟冒泡（只 写出每趟的结果）： 10 20 25 22 30 45 50 55 /第2趟 10 20 22 25 30 45 50 55 /第3趟 10
14、20 22 25 30 45 50 55 /第4趟 10 20 22 25 30 45 50 55 /第5趟 10 20 22 25 30 45 50 55 /第6趟 10 20 22 25 30 45 50 55 /第7趟 10 20 22 25 30 45 50 55 /第8趟 根据上面的讨论，冒泡排序的算法的框架为（设元素在a0an-1中）； for (i=n-1; i0; i-) 对a0ai进行冒泡； 进一步地，“a0ai进行冒泡”的实现为： for (j=0; jaj+1) t = aj; aj = aj+1; aj+1 = t; ,综合起来，就得到完整的冒泡排序程序： long S
15、ortBubble(int a, long n) /将a0an-1中的数按升序排列 int t; long i, j; for (i=n-1;i0; i-) for (j=0; jaj+1) t = aj; aj = aj+1; aj+1 = t; return 0; 该算法主要由两个嵌套的循环构成，显然是n2数量级的。,11.3.2 冒泡算法的改进,我们分析一下前面的冒泡排序算法，发现其每次冒泡，都机械地从起点比较到当前终点。事实上，若在某一次冒泡中，从某个位置起，后面都未进行过交换，则表明该位置后面的各元素已排好序。,例如，设某趟冒泡后，记录序列为： 序号： 0 1 2 3 4 5 6 记录：20 10 19 18 30 40 50 下趟冒泡时，当交换完20与18后（序号2与3），其后就没有再发生交换。这表明，序号3以后的元素，已经排好序，因此，下趟冒泡的终点到2号位置就可以了。这样，就可以减少冒泡的趟数。据此，我们可以通过控制冒泡次数改进前面的冒泡算法。具体做法是，将每次冒泡的终点由固定改为可调。在冒泡比较中，每交换一对元素，就将这对元素的第一个的序号（设为k）记下，当一趟冒泡后，k就是该趟中最后一次的交换位置，下趟比较的终点就可以设置为k。这样处理后，显然，若在一次冒泡中未交换任何记录，或k已退为0，则算法终止。,long SortB
