箱猫日和

【算法学习】趁热打铁，插入，选择和归并排序

插入排序

插入排序最直观的解释是不断拿扑克牌时排序的动作。一开始你只有一张8，第二张是5，你把5放在8的左边。第三张是9，你放在8的右边。第四张是2，你放在最左边。拿这四张牌的过程可以认为是排序4个数字的过程。步骤可以归纳为：

  • 拿起一张牌 -> 取下一个数
  • 比较现有牌，具体来说是从右往左找到第一个不小于当前牌的位置 -> 将所有大于当前数的数字向右移动一位
  • 放入牌 -> 放置数字

形象上来讲，放置数字的过程是多个数字右移的过程，所以不需要swap。Java代码如下：

public void sort(int[] xs) {
  int len = xs.length;
  if (len <= 1) return;
  for (int i = 1; i < len; i++) {
    int x = xs[i];
    int j = i;
    while (j > 0 && xs[j - 1] > x) {
      xs[j] = xs[j - 1];
      j--;
    }
    xs[j] = x;
  }
}

实际实现中，认为第一个数字即你只有一张牌的时候肯定是排好序的，所以插入牌的过程从第二个数字开始。注意着重看while部分，这就是大于当前数的数字右移的过程。

选择排序

现在理解起来其实不是很难的算法。之前没学好有可能是因为数据结构课太无聊，对数据结构课无爱……
核心想法是选择第一个小的数放在第一位，再在剩下的数字中选择第二小的数字放在第二位，依次类推。
理论上只看这些的话和冒泡排序很像，但是选择排序的特点是交换次数少，因为只记录下标，冒泡排序直接交换。Java代码如下：

private void swap(int[] ns, int i, int j) {
  if (i == j) return;
  int x = ns[i];
  ns[i] = ns[j];
  ns[j] = x;
}

public void sort(int[] ns) {
  int len = ns.length;
  for (int i = 0; i < len; i++) {
    int min = i;
    for (int j = i + 1; j < len; j++) {
      if (ns[j] < ns[min]) min = j;
    }
    swap(ns, i, min);
  }
}

注意选择排序只记录最小数字的下标，即min，swap理论上最多发生n次。

归并排序

如果理解了两个已排序的序列如何合并的过程的话基本上不难了。
归并排序的想法是把数组拆分为两个数组，排序这两个数组，再合并。过程中不断递归，直到只有1个元素。一个元素肯定是排序好的。然后向上回溯，由合并过程合并两个排序好的数组直到原始大小。
实际实现中，合并逻辑的两个输入数组是原始数组的两个邻接区间，其次有一个中间数组用来放置合并逻辑的输出。在回溯时要把中间数组的内容复制回原始数组。Java代码如下：

public void sort(int[] ns) {
  int[] ms = new int[ns.length];
  sort(ns, 0, ns.length - 1, ms);
}

private void sort(int[] ns, int begin, int end, int[] ms) {
  if (begin >= end) return;
  int center = (begin + end) / 2;
  sort(ns, begin, center, ms);
  sort(ns, center + 1, end, ms);
  merge(ns, begin, center, end, ms);
  System.arraycopy(ms, begin, ns, begin, end - begin + 1);
}

private void merge(int[] ns, int leftBegin, int leftEnd, int rightEnd,
    int[] ms) {
  int l = leftBegin, r = leftEnd + 1, i = leftBegin;
  while (l <= leftEnd && r <= rightEnd) {
    if (ns[l] < ns[r])
      ms[i++] = ns[l++];
    else
      ms[i++] = ns[r++];
  }
  while (l <= leftEnd)
    ms[i++] = ns[l++];
  while (r <= rightEnd)
    ms[i++] = ns[r++];
}

说一下合并逻辑，对两个输入数组或者一个数组的两个区间([leftBegin, leftEnd], [rightBegin, rightEnd]，因为是邻接的，所以rightBegin = leftEnd + 1），取两个数组的头一个元素比较，选择小的放入输出数组(ms），提供小数字的数组位置加1，依次类推。在第一个while结束时，肯定有一个数组的数字选完了。接下来要把生下来的数字放入输出数组。
排序的递归逻辑中最后一句是必须的，否则你等于没排序……这里使用了Java的System.arrayCopy，比逐个复制速度快。

到现在为止，学习的排序都是不需要特别的数据结构的，接下来可能要“复习”一下堆结构学习堆排序。

xnnyygn