下载掌阅APP，畅读海量书库
立即打开
现在让我们将注意力转向 排序： 重排数组中的所有元素——也称为 重排 数组——以便每个元素小于或者等于它的后继。我们要看到的第一种排序算法是选择排序，这是我能想到的最简单的算法，在设计一个排序算法时，我最先能想到的就是选择排序，虽然它远远不是最快的算法。
下面我们用依据作者名字对书架上的书排序这个例子来说明选择排序是如何运行的。从左向右查找整个书架，并且找到作者名字最先在字母表中出现的书籍。假定这本排序在字母表中最前的书籍是由Louisa May Alcott所写的（如果书架上包含由该作者所写的两本或者两本以上的书籍，选择它们中的任意一本）。将这个位置上的书籍和初始时位于位置1上的书籍进行调换。现在位于位置1上的书籍是作者名字最先在字母表中出现的书籍。现在沿着书架从左向右查找，查找从第2个位置到第 n 个位置上的书籍中最先在字母表中出现的书籍。并假定这本书是由Jane Austen所写的。将这本书与位于第2个位置的书籍进行调换，从而使得现在位于第1个位置和第2个位置上的书籍同时也是按照字母表排序中的位于最前面的第1个、第2个书籍。同理操作，得到位置3上应该放置的书籍，等等。一旦在位置 n -1处放置了正确的书籍（可能是由H.G.Wells所写的书），那么我们就完成操作了，因为这时仅仅就剩下一本书了（比如说，由Oscar Wilde所写的书），并且它就位于它本身应该放置的第 n 个位置处。
为了将这个方法转换成一个计算机算法，可以将书架看作是一个数组，所有的书看作是数组中的所有元素。下面是这个程序。
程序 SELECTION-SORT（ A , n ）
输入：
· A ： 一个数组 。
· n ： 待排序的数组 A 中的元素个数 。
结果： 数组 A 中的元素以非递减顺序排序 。
1. 令 i 从 1 到 n -1 依次取值 ：
A. 将 smallest 赋值为子数组 A [ i .. n ] 的最小元素的索引 。
B. 交换 A [ i ] 与 A [ smallest ] 的值 。
在 A [ i .. n ]中查找最小的元素相当于线性查找的变体。首先声明 A [ i ]是目前所看到的子数组中最小的元素，然后扫描子数组的剩余部分，每当发现有一个元素小于当前最小的元素时，我们就更新最小元素的索引。下面是重定义的程序。
程序 SELECTION-SORT（ A , n ）
输入和结果： 与之前的 Inputs 和 Result 相同 。
1. 令 i 从 1 到 n -1 依次取值 ：
A. 将 Smallest 赋值为 i 。
B. 令 j 从 i +1 到 n 依次取值 ：
.
如果
A
[
j
]<
A
[
smallest
]，
那么将
smallest
赋值为
j
。
C. 交换 A [ i ] 与 A [ smallest ] 的值 。
该程序有个“嵌套”循环，即第1B步中的循环嵌套在第1步中。对于外层循环的每次迭代，内层循环会执行它的循环体内的所有循环。注意内层循环的初始值 j 依赖于外层循环的当前值 i 。下图表明了选择排序在一个包含6个元素的数组中是如何进行排序的：
左上方是初始数组，每步展示了经过外层循环的一次迭代后的结果。深蓝色阴影的元素是当前得到的排好序的子数组。
如果你想使用循环不变式来证明SELECTION-SORT程序能正确地实现排序操作，那就需要对每个循环进行证明。程序太简单，我们不再证明其正确性，循环不变式如下：
第 1 步中的每次循环迭代开始时 ， 子数组 A [1.. i -1] 保存着整个数组 A 的前 i -1 个有序排列的最小元素 。
第 1B 步中的每次循环迭代开始时 ， A [ smallest ] 中存放着子数组 A [ i .. j -1] 中的最小元素 。
SELECTION-SORT的运行时间是多少？我们将证明它是Θ（ n 2 ）。关键是分析出内层循环执行了多少次迭代，其中每次迭代需要花费Θ（1）时间。（这里，因为在每次迭代中对 smallest 的赋值操作可能发生也可能不会发生，因此Θ符号的下界和上界中的常数因子可能是不同的。）让我们基于外部循环中循环变量 i 的值计算迭代的次数。当 i 等于1时，内层循环中 j 从2变化到 n ，共执行 n -1次。当 i 等于2时，内层循环中 j 从3到 n ，共执行 n -2次。外层循环中 i 值每增加1，那么内层循环执行次数会减少1次。总结可得，内层循环每次执行 n-i 次。在外层循环的最后一次迭代中，当 i 等于 n -1时，内层循环仅仅执行1次。因此内层循环迭代的总数是（ n -1）+（ n -2）+（ n -3）+…+2+1，这就是一个 等差数列求和 。根据等差数列的基本公式：对于任意非负整数 k 有
用 n -1代替 k ，我们看到内层循环迭代的总次数是（ n -1） n /2，即（ n 2 -n ）/2。使用渐近符号来省略低阶项（ -n ）和常数因子（1/2），那么我们就可以称内层循环的总次数是Θ（ n 2 ）。因此，SELECTION-SORT的运行时间是Θ（ n 2 ）。注意该运行时间能够覆盖所有情况。无论实际的元素值是什么，内层循环均会执行Θ（ n 2 ）次。
下面用另一种不使用等差数列的方法来证明运行时间是Θ（ n 2 ）。我们将分别证明运行时间是 O （ n 2 ）和Ω（ n 2 ），将渐近上界和渐近下界联合考虑就会得到Θ（ n 2 ）。为了证明运行时间是 O （ n 2 ），我们观察发现外部循环的每次迭代对应的内层循环最多执行 n -1次，而每次内层循环的迭代需花费常量时间，故外层循环的每次迭代需花费 O （ n ）时间。由于外部循环迭代 n -1次，即也是 O （ n ），故内层循环需要花费的总运行时间是 O （ n ）乘以 O （ n ），即 O （ n 2 ）。为了证明运行时间是Ω（ n 2 ），我们观察发现在外层循环的前 n /2次迭代中，每个内层循环至少迭代 n /2次，那么总执行次数至少为 n /2乘以 n /2，即 n 2 /4次。由于每个内层循环花费常量时间，所以我们证明出了运行时间至少是 n 2 /4的常数倍，即为Ω（ n 2 ）。
最后总结一下关于选择排序的两个结论。首先，我们看到渐近运行时间为Θ（ n 2 ），这是我们观察到的最坏的排序算法。第二，如果认真观察选择排序是如何运行的，你将发现Θ（ n 2 ）的运行时间来自第1 Bi 步中的比较操作。但是 移动 元素的次数仅仅是Θ（ n ），因为第1 C 步仅仅执行了 n -1次。如果移动元素相当耗时——或者它们所占空间很大或者它们储存在一个存储较慢的设备（例如磁盘）中——那么选择排序可能是一个合适的算法。