7.1. 简单排序算法的代码调优¶

既然排序是如此重要的应用，程序员自然会想优化自己的排序代码，让 它跑得更快。 当然，所有平方级排序（插入排序、冒泡排序和选择排序）都相对较慢。 正如"平方级"这个名字所暗示的，它们的最坏情况运行时间都是 \(\Theta(n^2)\) 。 让它们变快的最好办法是找到更好的排序算法。 尽管如此，多年来人们还是提出了许多关于如何加速这几种特定算法的 建议。 通过观察这些想法中哪些确实能带来更好的性能，我们可以学到关于代码 调优的有用经验。 观察这三种算法的相对性能，以及各种编程语言之间的比较，也很有 意思。

许多代码调优的尝试都采取类似的形式：先做一个测试。 如果测试成功，那么就可以跳过一些工作。 如果不成功，那么这些工作就需要完成。 在这种典型的代码调优中，跳过工作时就节省了时间。 然而，有几点需要考虑：

1. 跳过工作时节省了多少工作？

2. 这个测试多久通过一次？也就是说，有多大比例的时间节省了工作？

3. 进行这个测试的代价是多少？

测试通过得越频繁、节省的工作越多，优化带来的收益就越大。 测试的代价越高、失败得越频繁，收益就越小。 有时测试的代价超过了节省的工作，这种"代码调优"反而拖慢了程序。 既然人们通常并不会刻意去写低效代码，那么一个意在提速的想法并不 一定真的能让代码更快！ 因此，所有代码调优的尝试都应当在真实场景下进行实验测试，看看它们 是否真的带来了改进。

我们先试着加速插入排序。 回忆一下，插入排序反复把元素移向线性表已排序部分的前端，直到遇到 键值更小的记录为止。 在原始代码中，这是通过一系列交换操作完成的。 比起不断把记录向左交换直到找到更小的值，有一种更好的替代做法。 这就是把当前记录移到一个临时变量中，然后把所有键值更大的记录 向右移位一步。 由于交换每个元素需要三次赋值，而移位每个元素只需要一次赋值，我们 可以期望这能带来很大的改进。 当然，实际能获得多少改进取决于记录之间需要移动的量。 如果线性表本来就已经近乎有序，那么交换次数本来就不多。 下面是用这种优化实现的插入排序。

// Instead of swapping, "shift" the values down the array
void inssortshift(int[] A) {
  for (int i=1; i<A.length; i++) { // Insert i'th record
    int j;
    int temp = A[i];
    for (j=i; (j>0) && (temp < A[j-1]); j--)
      A[j] = A[j-1];
    A[j] = temp;
  }
}

// Instead of swapping, "shift" the values down the array
void inssortshift(T[] A) {
  for (int i=1; i<A.length; i++) { // Insert i'th record
    int j;
    T temp = A[i];
    for (j=i; (j>0) && (temp.compareTo(A[j-1]) < 0); j--) {
      A[j] = A[j-1];
    }
    A[j] = temp;
  }
}

// Instead of swapping, "shift" the values down the array
void inssortshift(Comparable* A[], int n) { // Insertion Sort
  for (int i=1; i<n; i++) { // Insert i'th record
    int j;
    Comparable* temp = A[i];
    for (j = i; (j > 0) && (*temp < *A[j-1]); j--)
      A[j] = A[j-1];
    A[j] = temp;
  }
}

现在，你可以测试一下自己是否理解它的工作原理。

表 11.7.1 显示了若干优化在四种场景下的相对代价： Java 解释执行代码、Java 用标准即时（Just-in-Time）编译器编译代码、 JavaScript 和 Python。

你所使用的编程语言会对程序的运行时间产生很大影响。 也许最大的区别在于语言是否编译。 Java 和 C++ 通常是编译型的，而 JavaScript 和 Python 通常是解释型的。 这会极大地影响某处代码改动究竟能否真正加速程序。 就"移位"与"交换"的取舍而言，移位总是能带来很大的改进。 对解释型语言 JavaScript 和 Python 来说，这一点比 Java 和 Processing 更为明显，但无论哪种情况都算是改进。 不过我们观察到的最显著效应是：执行同一个程序，Python 所需的时间 超过编译型 Java 代码的 100 倍（仍然比解释型 Java 代码慢一倍）。

有些语言有一些值得注意的特性。 事实证明，在 JavaScript 中用 i < n 还是 i != n 来测试循环 终止条件，会有很大差别。

转向冒泡排序，我们从这张表首先应当注意到：在随机输入上它比插入 排序慢得多。 我们来考虑一个有时被推荐用于冒泡排序的改进。 那就是在外层循环的每一轮迭代中检查该轮是否发生过交换，如果没有 就退出（因为此时我们知道线性表已经有序）。 我们还可以进一步改进这个想法：如果最后一次交换影响的是位置 \(i\) 和 \(i+1\) 处的值，那么位置大于 \(i\) 的值就 不可能再发生交换。 因此，我们再也不需要检查位置更靠后的值，即使靠前位置只有少量 交换，这也能省下许多轮迭代。 下面是用代码实现这种做法。

void bubblecheckswap(int[] A) {
    int n = A.length;
    while (n > 0) {
        int newn = 0;
        for (int i = 1; i < n; i++) {
            /* if this pair is out of order */
            if (A[i - 1] > A[i]) {
                swap(A, i - 1, i);
                newn = i;
            }
        }
        n = newn;
    }
}

void bubblecheckswap(T[] A) {
  int n = A.length - 1;
  while (n > 0) {
    int newn = 0;
    for (int i = 0; i < n; i++) {
      /* if this pair is out of order */
      if (A[i].compareTo(A[i+1]) > 0) {
        swap(A, i, i+1);
        newn = i;
      }
    }
    n = newn;
  }
}

void bubblecheckswap(Comparable* A[], int n) {
  n = n-1;
  while (n > 0) {
    int newn = 0;
    for (int i = 0; i < n; i++) {
      /* if this pair is out of order */
      if (*A[i] > *A[i+1]) {
        swap(A, i, i+1);
        newn = i;
      }
    }
    n = newn;
  }
}

这个想法的问题在于，要在内层循环中追踪最后一次交换的位置，需要 付出（相对而言）相当多的努力。 这种追踪过程是有代价的，只有当它节省的工作量大于它带来的工作量时， 这个代价才值得。 不幸的是，如表所示，在平均情况下它有时并不划算，具体取决于语言。 仅仅通过去掉追踪步骤来修改代码（这样既没有追踪的代价，也得不到 避免部分键比较的好处），在平均情况下几乎一样快。 当然，这是否总是成立，取决于提取记录键并比较它们的代价，而这 又取决于记录类型和排序实现的细节。 在我们的测试实现中，排序的是整数值，因此比较记录的代价比必须从 更复杂的对象中取出一个字段时要低。

追踪最后一次交换的位置确实也能显著改善最好情况的代价。 事实上，追踪最后一次交换的位置使冒泡排序的最好情况代价仅为 \(\Theta(n)\) 。 但如果这样做会给几乎所有其他输入增加额外代价，那么刻意人为地改善 最好情况就价值可疑了。 注意，只要在开头加上一段检查线性表是否已经有序的代码，我们名义上 就可以把 任意 排序算法的最好情况代价变成 \(\Theta(n)\) 。 显然这是浪费时间，尽管它有（很小的）大赚一笔的可能性。 插入排序的最好情况代价天然就是 \(\Theta(n)\) ，其时间与线性表 的"失序"程度成正比；与之不同，冒泡排序中通过交换检查所避免的迭代 轮数对失序记录的具体位置很敏感。 事实上，如果我们取一个有序线性表，把最小值移到最后，那么交换检查 就完全不会带来任何好处。

最后，我们来考虑选择排序。 这张表首先表明，选择排序可以看作是对冒泡排序远比追踪最后一次交换 位置更好的优化。 也就是说，追踪最大元素的位置并执行一次交换把它放到正确位置，比 追踪最近一次交换的位置要好得多。 不过，也许令人意外的是，在 Python 中并非如此。 另一方面，这张表还表明，在选择 Java 解释执行形式实现时，选择排序 在平均情况下比未优化的插入排序更快。 显然，在这种情形下交换的代价很高。

我们最初的选择排序实现即使在当前记录已经位于正确位置时，也会调用 swap 。 例如，如果值最大的记录已经在数组最右端的位置， selsort 仍然会 用两个相同的位置参数调用 swap 。 最终的效果是 swap 所做的工作不会改变数组中的任何内容，这纯粹 是浪费时间。 因此，选择排序在最好、平均和最坏情况下执行的交换总次数始终是 \(n-1\) 。 在调用 swap 之前先测试两个位置是否相同，看起来似乎是个好主意， 尤其是选择排序最出名的特点就是交换次数少。 实际上，我们不能指望这会产生多大差别，因为我们谈论的是 \(\Theta(n^2)\) 总步数中的 \(\Theta(n)\) 次操作，这是一个 无足轻重的比例。 另一个考虑是：即便只考虑执行交换所需的时间，这是否通常也能节省 时间。 检查一次交换是否必要本身也要花一些时间。 只有当测试所需的时间能够被避免那次不必要交换所节省的工作充分补偿 时，这个测试才值得。 对于随机顺序的输入，在每次交换前测试这个条件可能比直接交换更昂贵。 如果输入记录本来就有序，那么所有交换都是不必要的，测试（显然）会 更快。 但在平均情况下，这样只能省下很少的交换，这种"优化"实际上可能拖慢 程序（不过只是略微拖慢）。

对于所有这些排序算法， swap 函数调用都可能是开销的关键部分， 因为它被调用的次数太多了。 一种简单的加速方法是把这个函数调用替换为该函数会执行的代码。 取决于语言、编译器和操作系统，这样做有望节省总时间的 5% 到 10%。 另一方面，好的编译器实际上会自动做同样的事情。

另一个重要的考虑是所使用的数据对象类型。 对于 Java，我们使用简单的 int 数组，因此不需要从对象中解引用 键值。 如果我们使用更复杂的 KVPair 对象，代价将比表中 Java 一列所示 的数值大幅增加。 JavaScript 和 Python 已经在付出这个代价，因为它们没有原始 int 的概念，而是把整数实现为对象。