3.2　基于遍历的排序

与上面讨论的选择与查找问题关注单个元素所不同，排序问题关注的是在一组元素之间建立序关系，它要求将一组可比较大小的元素(即一个全序集)排成依次增大或者减小的线性序列。为了简化讨论，在不予特别说明时，我们均假设待排序的元素是各不相同的，并且的目标是将所有元素从小到大排列。显然这些假设是非限制性的，我们后续所给出的算法均可以处理元素值相同、从大到小排序等情况，只需要进行一些细节的修改。根据上面的说明，我们定义排序问题如下。
定义3.3（排序问题）
●输入：一组各不相同的有序的元素。
●输出：输入元素的某个排列，满足a′1不作特别说明时，我们主要考虑“基于比较的排序”(comparison-based sorting)，即计算模型提供了比较元素大小的关键操作，并且只能使用该比较操作来决定元素之间的序。
为了在所有元素对之间建立序关系，我们可以使用两层嵌套的线性表遍历来实现。基于这一思路，我们可以得出基于遍历的排序算法，包括选择排序、插入排序、冒泡排序等。
3.2.1　选择排序
如果知道一组元素中的最大元素是哪个，则我们就可以将最大值元素放到线性表的末尾。对于剩下的元素反复进行上述“选最大”的过程，我们就可以完成一组元素的排序。这就是“选择排序”算法的基本原理，其实现如算法4所示。算法4：SELECTION-SORT(A［1..n］)
1　for i∶=n downto 2 do
2　index-of-max∶=SELECT-MAX(A［1..i］);/调用算法3/
3　SWAP(A［index-of-max］,A［i］);/将数组中指定位置的两个元素互换/选择排序的运作非常“规整”，这简化了算法复杂度的分析。具体而言，无论输入的元素是何种情况，选择排序总是先对所有n个元素遍历选最大值，其次对剩下的n－1个元素遍历选最大值……最终对剩下的两个元素选最大值。因此选择排序的最坏情况与平均情况时间复杂度同样为：W(n)=A(n)=∑n－1i=1i=n(n－1)2=Θ(n2)选择排序在原地对输入元素进行比较与互换，它的空间复杂度始终为O(1)，即选择排序的空间消耗与输入的规模是无关的。我们将所有空间复杂度为O(1)的排序算法称为原地排序(in-place sorting)。
冒泡排序(算法6)也是一种简单且常用的基于遍历的排序，其基本原理与选择排序类似，我们将关于冒泡排序的讨论留作习题。
3.2.2　插入排序
深入分析选择排序，我们发现它有一个明显的问题：无论输入元素的乱序程度如何，算法总是进行相同的操作。此时一种合理的期望是，当输入元素较为有序时，相对输入元素更为乱序的情况而言，排序算法应该能进行较少的元素比较。为此我们提出插入排序，它的基本原理仍然是线性表的两层嵌套遍历，但是它能够利用输入元素较为有序的特点。具体而言，在插入排序时，对于一组排好序的元素，当要插入一个新的元素时，通过遍历整个序列，我们总可以找到正确的插入位置；依次将元素插入到有序序列中正确的位置，则可以完成所有元素的排序。插入排序的实现如算法5所示。通过下面的分析将看到，插入排序对于更有序的输入序列将使用更少的比较操作。算法5：INSERTION-SORT(A［1..n］)
1　for j∶=2 to n do
2　temp∶=A［j］;
3　i∶=j－1;
4　while i>0 and A［i］>temp do
5　A［i+1］∶=A［i］;
6　i∶=i－1;7　A［i+1］∶=temp;我们同样可以通过数学归纳法来证明插入排序的正确性。对于任意n个输入元素，插入排序的过程可以分为n个阶段，其中第i(1≤i≤n)个阶段对应于进行第i次插入的过程。对于从任意第i阶段进展到第i+1阶段，要证明的归纳不变式是：插入完成后，被插入的序列是有序的。通过分析插入排序的操作，我们很容易证明这一结论，详细证明留作习题。
分析插入排序的运作过程，我们发现其中的一个关键的步骤是将一个待处理的元素插入到一个已经有序的序列中。这一操作的代价可以有较大范围的变化。具体而言，假设i个元素已经通过前面的插入操作排好序，现在需要将第i+1个元素x通过比较插入到前i 个元素中的某个位置，如图3.1所示。不失一般性，假设从后往前依次将待插入的元素与这i个元素进行比较。我们最多需要与i个有序元素中的每一个进行比较；最少只需要与最后一个元素进行比较。
图3.1　插入排序平均情况时间复杂度分析
首先分析最坏情况时间复杂度。在插入排序执行过程中，待插入序列的长度依次为1,2,3,…,n－1，而每次插入最多与待插入序列中的每个元素均进行比较，所以插入排序的最坏情况时间复杂度为：W(n)=∑n－1i=1i=n(n－1)2=Θ(n2)很容易构造出这样一个导致最坏情况的输入序列。当待排元素从大到小排列时，插入排序算法会做最多次的元素比较。
虽然插入排序的最坏情况时间复杂度与选择排序是同样的，但是从前面的分析中我们已经看到，插入过程的代价是可以有较大变化的，这将体现为平均情况时间复杂度的改进。具体而言，假设所有可能的输入序列以相等的概率出现，我们先来分析插入算法执行的一般情况，如图3.1所示。
假设i个元素已经通过前面的插入操作排好序，现在需要将第i+1个元素x通过比较插入到前i 个元素中的某个位置。前i个元素*有i+1个可能的空位。由于假设所有可能的输入等概率地出现，所以此时元素x在所有i+1个可能被插入的位置中也是等概率出现的。此时插入元素x 所需比较次数的期望值为：ci+1=1i+1∑ij=1j右边i个位置+1i+1i最左边1个位置
=i2+1－1i+1进而有插入排序的平均情况时间复杂度为：A(n)=∑n－1i=1ci+1
=n(n－1)4+n－1－∑nj=21j
=n24+3n4-(lnn+γ+ε(n)－1)
=Θ(n2)比较插入排序的平均情况与最坏情况时间复杂度，我们发现代价大约减少一半。插入排序的平均情况时间复杂度同样比选择排序的平均情况时间复杂度大约减少一半。也就是说，插入排序能够较好地利用输入元素较为有序的有利条件。