例9.2.1设顺序表中有15个记录，它们的关键字依次为：
{6，8，15，17，27，34，45，66，74，89，100，112，124，144，160}
用二分查找法在该顺序表中查找关键字为27（存在）和130（不存在）的记录。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
6 8 15 17 27 34 45 66 74 89 100 112 124 144 160
low mid high
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
6 8 15 17 27 34 45 66 74 89 100 112 124 144 160
low mid high
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
6 8 15 17 27 34 45 66 74 89 100 112 124 144 160
low mid high
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
6 8 15 17 27 34 45 66 74 89 100 112 124 144 160
low mid high
图9.2.1(a) 查找关键字为27的记录
时间复杂度:O(log2n)
1.8 排序技术
排序(sorting)是把一个无序的数据元素序列整理成有规律的按排序关键字递增(或递减)排列的有序序列的过程。
1.8.1 交换类排序法 1. 冒泡排序
冒泡排序:这种排序方法的基本思想是:
将待排序序列中第一位置的关键字R1.key与第二个位置的关键字R2.key作比较， 如果R1.key>R2.key，则交换记录R1和R2在序列中的位置，否则不交换； 然后继续对当前序列中的第二个记录和第三个记录作同样的处理，依次类推，直到序列中最后一个记录处理完为止，我们称这样的过程为一次冒泡排序。
通过第一次冒泡排序，最大（或最小）的记录排到了序列的最后一个位置上。然后对序列中的前n-1个记录重复进行冒泡排序，对于具有n个记录的序列，进行n-1次冒泡排序。
当进行某次冒泡排序时，若没有任何两个记录交换位置，则表明序列巳按记录关键字非递减的顺序排列，此时排序也可结束。
例 有八个记录，它们的初始关键字序列为{38,5,19,26,49,97,1,66},用冒泡排序法对它们进行排序。
该序列的冒泡排序过程如图8.4.1所示。 初始关键字序列: 38 5 19 26 49 97 1 66 第一次排序结果 5 19 26 38 49 1 66 [97] 第二次排序结果 5 19 26 38 1 49 [66 97] 第三次排序结果 5 19 26 1 38 [49 66 97] 第四次排序结果 5 19 1 26 [38 49 66 97] 第五次排序结果 5 1 19 [26 38 49 66 97] 第六次排序结果 1 5 [19 26 38 49 66 97] 第七次排序结果 1 5 19 26 38 49 66 97
2. 快速排序
快速排序(quick sort)又叫作分区交换排序，是目前已知的平均速度最快的一种排序方法，它是对冒泡排序方法的一种改进。快速排序方法的基本思想是:
从待排序的n个记录中任意选取一个记录Ri(通常选取序列中的第一个记录)作标准，调整序列中各个记录的位置，使排在Ri前面的记录的关键字都小于Ri.key，排在Ri后面的记录的关键字都大于等于Ri.key，我们把这样的一个过程称作一次快速排序。在第一次快速排序中，确定了所选取的记录Ri 最终在序列中的排列位置，同时也把剩余的记录分成了两个子序列。分别进行快速排序，又确定了两个记录在序列中应处的位置。并将剩余记录分成了四个子序列。如此重复下去。当各个子序列的长度为1时。全部记录排序完毕。
60
(初始序列) 60 55 48 37 10 90 84 36
i j
(1) 36 55 48 37 10 90 84 □
i j
(2) 36 55 48 37 10 90 84 □
i j
(3) 36 55 48 37 10 90 84 □
j i
(4) 36 55 48 37 10 90 84 □
i j
(5) 36 55 48 37 10 90 84 □
i j
(6) 36 55 48 37 10 □ 84 90
i j
(7) 36 55 48 37 10 □ 84 90
i j
(8) 36 55 48 37 10 60 84 90
图8.4.2 第一次快速排序
初始关键字序列[60 55 48 37 10 90 84 36]
(1) [36 55 48 37 10] 60 [84 90]
(2) [10] 36 [48 37 55] 60 [84 90]
(3) 10 36 [37 48 55] 60 [84 90]
(4) 10 36 [37] 48 [55] 60 [84 90]
(5) 10 36 37 48 [55] 60 [84 90]
(6) 10 36 37 48 55 60 [84 90] (7) 10 36 37 48 55 60 84 [90] (8) 10 36 37 48 55 60 84 90 图8.4.3 快速排序
1. 简单（直接）插入排序
直接插入排序的基本思想是：顺序地把待排序序列中的各个记录按其关键字的大小，插入到已排序的序列的适当位置。
假设待排序序列为R1，R2，?，Rn，开始排序时，认为序列中第一个记录已排好序，它组成了排序的初始序列；
现将第二个记录的关键字与第一个记录的关键字进行比较，若R1.key＞ R2．key，则交换这两个记录的位置，否则不交换，这样就将第二个记录插入到了已排序的序列中。
依次类推，对序列中的第i个记录Ri排序时，Ri前面的i－1个记录已组成了有序序列R1'，R2'，?，Ri-1'，将Ri．key依次与Ri-1'.key，Ri-2'.key?进行比较，找出一个合适的j（1<=j<=i-1)，使得Ri-1'.key<=Ri.key 例 已知有6个待排序的记录，它们的关键字分别为65，4，8，78，6，26，用直接插入法进行排序。 初始关键字序列：[65] 4 8 78 6 26 第一次排序： [4 65] 8 78 6 26 第二次排序： [4 8 65] 78 6 26 第三次排序： [4 8 65 78] 6 26 第四次排序： [4 6 8 65 78] 26 第五次排序： [4 6 8 26 65 78] 图8.3.1 直接插入排序 2 直接插入排序的时间复杂度为O(n)或n(n+1)次比较。 2. 希尔排序 希尔（shell排序）又称作缩小增量排序，它的基本思想是：不断把待排序的记录分成若干个小组，对同一组内的记录进行排序，在分组时，始终保证当前组内的记录个数超过前面分组排序时组内的记录个数。 希尔排序具体的作法是：先设置一个整数量d1，称之为增量，将待排序的记录序列中所有距离为d1的记录放在同一组中。例如，若 d1=5，则记录R1,R6,R11?放在同一组中，记录R2,R7，R12?放在另一组中，如此类推。然后对各组内的记录分别进行排序，这样的一次分组排序过程称为一次排序。再设置另一个新的增量d2，使d2< d1，采用上述相同的方法继续进行第二次排序?如此进行下去，当最后一次排序时，设置的增量di=1时，表明序列中全部记录放在了同一组内，该次排序结束时，整个序列的排序工作完成。在希尔排序的各次排序过程中，组内记录的排序可以采用前面介绍的直接插入排序法，也可采用其他合适的方法。 例 设待排序的序列中有12个记录，它们的关键字分别为65，34，25，87，12，38，56， 46，14，77，92，23，用希尔排序法进行排序。 图8.3.2给出了该序列的希尔排序过程示意图，图中在同一连线上的关键字表示它们所属的记录放在同一组中。 缩小增量一般取: ht=n/2(k=1,2,,log2n) 1.5 次数接近于O(n) 初始关键字序列 65 34 25 87 12 38 56 46 14 77 92 23 65 34 25 87 12 38 56 46 14 77 92 23 结果序列 56 34 14 77 12 23 65 46 25 87 92 38 (a) 第一次排序 56 34 14 77 12 23 65 46 25 87 92 38 结果序列 56 12 14 65 34 23 77 46 25 87 92 38 (b) 第二次排序 56 12 14 65 34 23 77 46 25 87 92 38 (c) 第三次排序 图8.3.2 希尔排序 1.8.3 选择排序 选择排序的基本思想是:不断从待排序的序列中选取关键字最小的记录放到已排序的记录序列的后面，直到序列中所有记录都巳排序为止。 两种常用的选择排序方法是直接选择排序和堆排序。堆排序是一种时间复杂度为O(n(log2n))的排序方法。 1. 简单（直接）选择排序 直接选择排序(straight selection sort)是一种简单且直观的排序方法。直接选择排序的做法是:从待排序的所有记录中，选取关键字最小的记录并将它与原始序列中的第一个记录交换位置；然后从去掉了关键字最小的记录的剩余记录中，选择关键字最小的记录并将它与原始序列中第二个记录交换位置??如此重复下去，直到序列中全部记录排序完毕。 例 用直接选择法进行排序。 图8.5.1为直接选择排序过程示意图，其中方括号[]中为已排序的记录的关键字。 初始关键字序列: [65] 4 8 78 6 26 第一次排序结果: [4] 65 8 78 6 26 第二次排序结果: [4 6] 8 78 65 26 第三次排序结果: [4 6 8] 78 65 26 第四次排序结果: [4 6 8 26] 65 78 第五次排序结果: [4 6 8 26 65] 78 最后结果序列: [4 6 8 26 65 78] 图8.5.1 直接选择排序 k 2. 堆排序 堆树的定义 1. 最大树和最小树定义 52 8 30 30 50 52 20 12 17 17 5 4 52 50 5 (a) (b) (c) 52 52 30 52 30 52 17 5 4 17 5 4 (d) (e) 图5.7.5 最大树或最小树 堆树的定义 堆树简称为堆，是一棵二叉树。堆有如下特征： 堆树是一棵完全二叉树，如果一棵完全二叉树本身又满足最大树的条件，则这棵完全二叉树就是最大堆；如果一棵完全二叉树本身又满足最小树的条件，则这棵完全二叉树就是最小堆。 唯一满足堆树要求的是(d)所示的二叉树，它是一棵完全二叉树，且它满足最大树的概念，也就是说，它是最大堆。 堆排序问题是数据排序的一种经典方法。这种方法的思想是： 首先将堆顶元素（最大结点）移到结果数据存储空间，再从堆中余下的结点（左子树或右子树）中选出一个最大结点，移到堆顶，即将堆中余下的结点重新“调整”为一个新堆，再将堆顶结点移到结果数据存储空间的下一个空间位置，如此下去，直到所有的结点都被移到结果数据存储空间。那么，结果存储空间中的数据就是按从大至小的排列。 在堆排序中有两个关键的问题：实际中很难碰到一棵开始就是堆的树，如何构造一个初始堆树就是第一个关键问题；有了初始堆，在排序时，当移走根结点时，对余下的树又如何再“调整”为一棵新堆，这是第二个关键问题。 构造N所指结点为根的堆算法思想： A. 先将N所指结点的值复制到一个工作空间中临时存放。 B. 再将N所指结点的孩子中，值较大的与工作空间中的值比较： (1) 如果工作空间中值更大，新堆已经形成，就将工作空间中的值存放到N所指的 位置，结束。 C. 如果某个孩子的结点值更大，则将这个值存放到这个孩子双亲的结点位置，即N 位置。此时，工作空间中的结点还未找到存放位置，再将上移的孩子结点位置作为N所指的新位置，转到B步骤。