8.1 排序算法的下界

插入排序算法作用域包含三个元素的输入序列的决策树情况

alt

最坏情况的下界

在决策树中，从根节点到任意一个可达叶结点之间最长简单路径的长度，表示的是对应的排序算法中最坏情况下的比较次数。

因此，一个比较排序算法中的最坏情况比较次数就等于其决策树的高度。

同时，当决策树中每种排列都是以可达的叶结点的形式出现时，该决策树高度的下界也就是比较排序算法运行时间的下界。

下面的定理给出这样的一个下界。

定理 8.1

在最坏情况下，任何比较排序算法都需要做Ω (nlgn)次比较。 alt

推论 8.2

堆排序和归并排序都是渐进最优的比较排序算法。

证明

堆排序和归并排序的运行时间上界为O(nlgn)，这与定理8.1给出的最坏情况的下界Ω(nlgn)是一致的。

8.1-3

alt

Solution

alt

8.2 计数排序

伪代码 过程 COUNTING-SORT
//输入是一个数组A[1..n]，A.length=n
//B[1..n]存放排序的输出
//C[0..k]提供临时存储的空间
COUNTING-SORT(A,B,k)
  let C[0..k] be a new array
  //数组C的值被置为0
  for i = 0 to k
    C[i] = 0
  //遍历每一个输入元素，如果一个输入元素的值为i，就将C[i]值加1
  for j = 1 to A.length
    C[A[j]] = C[A[j]] + 1//C[i]中保存的就是等于i的元素的个数
  //C[i] now contains the number of elements equal to i
  //通过加总计算确定对每一个i-0,1,……,k,有多少输入元素是小于或等于i的
  for i = 1 to k
    C[i] = C [i] + C[i-1]
  //C[i] now contains the number of elements less than or equal to i
  //把每个元素A[j]放到它在输出数组B中的正确位置上
  for j = A.length downto 1
    B[C[A[j]]] = A [j]
    C[A[j]] = C[A[j]] - 1
计数排序的运行过程

alt

8.2-1

Using Figure 8.2 as a model, illustrate the operation of COUNTING-SORT on the array A =⟨6,0,2,0,1,3,4,6,1,3,2⟩.

以图8.2为模型，说明数组a上计数排序的操作=⟨6,0,2,0,1,3,4,6,1,3,2⟩.

Solution

我们有那个C=⟨2,4,6,8,9,9,11⟩. 然后，在第10-12行循环的连续迭代之后，我们得到

B=⟨,,,,,2.⟩,

B=⟨,,,,,2,3,,,⟩,

B=⟨,,,1,,2,3,,,⟩

最后，

B=⟨0,0,1,1,2,2,3,3,4,6,6⟩.

8.3 基数排序

基数排序是先按最低有效位进行排序来解决卡片排序问题的。

“一叠”7张3位数卡片的基数排序过程

alt

伪代码 过程 RADIX-SORT(A,d)
//n个d位的元素存放在数组A中，其中第1位是最低为，第d位是最高位
RADIX-SORT(A,d)
for i = 1 to d
use a stable sort to sort array A on digit i

8.3-1

Using Figure 8.3 as a model, illustrate the operation of RADIX-SORT on the following list of English words: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX.

以图8.3为模型，在以下英文单词列表中说明基数排序的操作：COW、DOG、SEA、RUG、ROW、MOB、BOX、TAB、BAR、EAR、TAR、DIG、BIG、TEA、NOW、FOX。

Solution

alt

8.3-4

alt

Solution

首先运行整数列表，并将每个整数转换为基数n，然后对它们进行基数排序。每个数字最多有3位数字，因此只需通过alt 次。对于每个过程，有n个可能的值可以采用，因此我们可以使用计数排序在O（n）时间内对每个数字进行排序。

8.4 桶排序

伪代码 过程
//输入：一个包含n个元素的数组A，且每个元素A[i]满足0≤A[i]＜1
//一个临时数组B[0..n-1]来存放链表（即桶），并假设存在一种用于维护这些链表的机制
BUCKET-SORT(A)
  n = A.length
  let B[0..n-1] be a new array
  for i = 0 to n-1
    make B[i] an empty list
  for i = 1 to n
    insert A[i] into list B[⌊nA[i]⌋]
  for i = 0 to n-1
    sort list B[i] with insertion sort
  concatenate the lists B[0],B[1],...,B[n-1] together in order
在一个包含10个元素的输入数组上的桶排序过程

alt

8.4-1

Using Figure 8.4 as a model, illustrate the operation of BUCKET-SORT on the array A=⟨.79,.13,.16,.64,.39,.20,.89,.53,.71,.42⟩.

以图8.4为模型，说明了BUCKET-SORT在数组A=⟨.79,.13,.16,.64,.39,.20,.89,.53,.71,.42⟩上的操作。

Solution

alt

A=⟨.13,.16,.20,.39,.42,.53,.64,.71,.79,.89⟩.

8.4-2

alt

Solution

如果所有的键都落在同一个bucket中，并且它们恰好是以相反的顺序排列的，那么我们必须使用插入排序将一个bucket中的n个项按相反的顺序排序。这是Θ（n^2）。

我们可以使用合并排序或heapsort来提高最坏情况下的运行时间。选择插入排序是因为它在链表上运行良好，链表具有最佳时间，并且对于短链表只需要恒定的额外空间。如果我们使用另一种排序算法，我们必须将每个列表转换为一个数组，这在实践中可能会减慢算法的速度。