《算法基础：打开算法之门》一3.2 选择排序

本节书摘来自华章出版社《算法基础：打开算法之门》一书中的第3章，第3.2节，作者 ［美］托马斯 H 科尔曼（Thomas H Cormen），更多章节内容可以访问云栖社区“华章计算机”公众号查看

3.2 选择排序

现在让我们将注意力转向排序：重排数组中的所有元素——也称为重排数组——以便每个元素小于或者等于它的后继。我们要看到的第一种排序算法是选择排序，这是我能想到的最简单的算法，在设计一个排序算法时，我最先能想到的就是选择排序，虽然它远远不是最快的算法。

下面我们用依据作者名字对书架上的书排序这个例子来说明选择排序是如何运行的。从左向右查找整个书架，并且找到作者名字最先在字母表中出现的书籍。假定这本排序在字母表中最前的书籍是由Louisa May Alcott所写的（如果书架上包含由该作者所写的两本或者两本以上的书籍，选择它们中的任意一本）。将这个位置上的书籍和初始时位于位置1上的书籍进行调换。32现在位于位置1上的书籍是作者名字最先在字母表中出现的书籍。现在沿着书架从左向右查找，查找从第2个位置到第n个位置上的书籍中最先在字母表中出现的书籍。并假定这本书是由Jane Austen所写的。将这本书与位于第2个位置的书籍进行调换，从而使得现在位于第1个位置和第2个位置上的书籍同时也是按照字母表排序中的位于最前面的第1个、第2个书籍。同理操作，得到位置3上应该放置的书籍，等等。一旦在位置n-1处放置了正确的书籍（可能是由HGWells所写的书），那么我们就完成操作了，因为这时仅仅就剩下一本书了（比如说，由Oscar Wilde所写的书），并且它就位于它本身应该放置的第n个位置处。
为了将这个方法转换成一个计算机算法，可以将书架看作是一个数组，所有的书看作是数组中的所有元素。下面是这个程序。

在A［in］中查找最小的元素相当于线性查找的变体。首先声明A［i］是目前所看到的子数组中最小的元素，然后扫描子数组的剩余部分，每当发现有一个元素小于当前最小的元素时，我们就更新最小元素的索引。下面是重定义的程序。

该程序有个“嵌套”循环，即第1B步中的循环嵌套在第1步中。对于外层循环的每次迭代，内层循环会执行它的循环体内的所有循环。注意内层循环的初始值j依赖于外层循环的当前值i。下图表明了选择排序在一个包含6个元素的数组中是如何进行排序的：

左上方是初始数组，每步展示了经过外层循环的一次迭代后的结果。灰色阴影的元素是当前得到的排好序的子数组。如果你想使用循环不变式来证明SELECTIONSORT程序能正确地实现排序操作，那就需要对每个循环进行证明。程序太简单，我们不再证明其正确性，循环不变式如下：第1步中的每次循环迭代开始时，子数组A［1i-1］保存着整个数组A的前i-1个有序排列的最小元素。第1B步中的每次循环迭代开始时，A［smallest］中存放着子数组A［ij-1］中的最小元素。SELECTIONSORT的运行时间是多少？我们将证明它是Θ（n2）。关键是分析出内层循环执行了多少次迭代，其中每次迭代需要花费Θ（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，34这就是一个等差数列求和。根据等差数列的基本公式：对于任意非负整数k有

用n-1代替k，我们看到内层循环迭代的总次数是(n-1)n/2，即(n2-n)/2。使用渐近符号来省略低阶项(-n)和常数因子(1/2)，那么我们就可以称内层循环的总次数是Θ（n2）。因此，SELECTIONSORT的运行时间是Θ（n2）。注意该运行时间能够覆盖所有情况。无论实际的元素值是什么，内层循环均会执行Θ（n2）次。下面用另一种不使用等差数列的方法来证明运行时间是Θ（n2）。我们将分别证明运行时间是O（n2)和Ω(n2)，将渐近上界和渐近下界联合考虑就会得到Θ（n2）。为了证明运行时间是O（n2)，我们观察发现外部循环的每次迭代对应的内层循环最多执行n-1次，而每次内层循环的迭代需花费常量时间，故外层循环的每次迭代需花费O（n)时间。由于外部循环迭代n-1次，即也是O（n)，故内层循环需要花费的总运行时间是O（n)乘以O（n)，即O（n2)。为了证明运行时间是Ω(n2)，我们观察发现在外层循环的前n/2次迭代中，每个内层循环至少迭代n/2次，那么总执行次数至少为n/2乘以n/2，即n2/4次。由于每个内层循环花费常量时间，所以我们证明出了运行时间至少是n2/4的常数倍，即为Ω(n2)。最后总结一下关于选择排序的两个结论。首先，我们看到渐近运行时间为Θ（n2），这是我们观察到的最坏的排序算法。第二，如果认真观察选择排序是如何运行的，你将发现Θ（n2）的运行时间来自于第1Bi步中的比较操作。但是移动元素的次数仅仅是Θ（n），因为第1C步仅仅执行了n-1次。如果移动元素相当耗时——或者它们所占空间很大或者它们储存在一个存储较慢的设备（例如磁盘）中——那么选择排序可能是一个合适的算法。