Dart 算法篇 | 插入排序

1.源码中的 Sort 排序

在 sky_engine/lib/internal/sort.dart 中有一个 Sort 类，其中 sortRange 方法可以进行排序。可以看出 sortRange 方法是对 List 索引范围区间进行排序。

1---->[sky_engine/lib/internal/sort.dart]----
2static void sortRange<E>(List<E> a, int from, int to, int compare(E a, E b)) {
3  if ((from < 0) || (to > a.length) || (to < from)) {
4    throw "OutOfRange";
5  }
6  _doSort(a, from, to - 1, compare);
7}


在 _doSort 方法中，当待排序的元素树小于等于 _INSERTION_SORT_THRESHOLD 时，使用 _insertionSort ，即插入排序。否则，使用 _dualPivotQuicksort ，即双基准快速排序。可以看出，当待排序元素比较少的时候，插入排序要更优越一些。

1static const int _INSERTION_SORT_THRESHOLD = 32;
2
3static void _doSort<E>(
4    List<E> a, int left, int right, int compare(E a, E b)) {
5  if ((right - left) <= _INSERTION_SORT_THRESHOLD) {
6    _insertionSort(a, left, right, compare);
7  } else {
8    _dualPivotQuicksort(a, left, right, compare);
9  }
10}


2.插入排序的实现

下面是 Sort#_insertionSort 的实现逻辑。这是某数组，制定索引区间的元素进行快速排序的算法，更具有普适性。

1static void _insertionSort<E>(
2    List<E> a, int left, int right, int compare(E a, E b)) {
3  for (int i = left + 1; i <= right; i++) {
4    var el = a[i];
5    int j = i;
6    while ((j > left) && (compare(a[j - 1], el) > 0)) {
7      a[j] = a[j - 1];
8      j--;
9    }
10    a[j] = el;
11  }
12}


3.测试代码

由于 Sort 类是 _internal 包的一部分，无法再外界使用。

1main() {
2  List<int> arr = [10, 16, 35, 6, 21, 77];
3  Sort.insertionSort<int>(arr, 0, arr.length - 1, (a, b) => a.compareTo(b));
4  print(arr); // [6, 10, 16, 21, 35, 77]
5}
6
7class Sort {
8  static void insertionSort<E>(
9      List<E> a, int left, int right, int compare(E a, E b)) {
10    for (int i = left + 1; i <= right; i++) { // tag1
11      var el = a[i];
12      int j = i; 
13      while ((j > left) && (compare(a[j - 1], el) > 0)) { // tag2
14        a[j] = a[j - 1];
15        j--;
16      }
17      a[j] = el; // tag3
18    }
19  }
20}


4.算法分析

从待排序的索引区间为 [left，right] ， tag1 表明，变量 i 从 left + 1 索引开始向后遍历。然后，定义临时变量 el ，其值为列表中索引为 i 的元素。接着定义临时变量 j ，其值为 i 。

tag2 处的 while 循环可能不怎么好理解，那就好好理一下。

首先，当 while 中的条件满足时，会执行 循环体 ，所以要理解这个循环，要明白它的循环条件是什么。

如下，是 i = left+1 时的切片，j 的初始值为 i 。循环体执行的条件是 j > left 且 前一个元素比 el 大 ，如下的示意图中，可见第二个条件不满足，所以不会执行 while 循环体。

此时在 tag3 处， a[j] = el ，此时 i 和 j 一致，所以数组在 i = left + 1 这个循环切片中没有变化。然后则进行到 i = left + 2 循环中。

在 i = left + 2 时，j 将从 i 索引开始，当前 el=a[i]=35 ， 前一个元素比 el 大 的条件也是不满足的。所以同理，也不会进入   while 循环体，接下来进行到 i = left + 3 循环。

在 i = left + 3 时，j 将从 i 索引开始，当前 el=a[i]=6 ， while 循环条件满足，将会进入循环体。

1while ((j > left) && (compare(a[j - 1], el) > 0)) {
2  a[j] = a[j - 1];
3  j--;
4}


循环体中，将 a [j-1] 的值赋给 2[j] ，然后 j-- 。如下图，是第一次 while 循环执行过后的情况，此时切片中 j = left +2 ， a[j-1] 仍比前 el =6 大， while 循环条件仍满足，所以会继续执行循环体。

如下图，是第二次 while 循环执行过后的情况，此时   j = left + 1 ， while 循环条件仍满足，所以会继续执行循环体。

如下图，是第三次 while 循环执行过后的情况，此时   j = left + 1 ， while 循环条件中的 j>left 条件不满足，所以 while 循环结束。

while 循环结束后，会执行 tag3 ，也就是 a[j] = el ，这样就完成了 6 元素的前移。插入排序会在每次 i 的前进后，将 i 及之前的元素排好序。这样的好处是：待排序元素前的元素都已排序，如果下一元素大于前驱，则无需进入循环体，直接进入下一循环。

如下对于 21 的排序，由于 21 > 16 ， while 循环只需执行 1 次就能到达恰当的位置。77 比 35 大，不会执行循环体，这样就可以减少很多不必要的比较。

小批量的数据使用插入排序是不错的选择，但对于大量的数据插入排序的表现就不行了。从算法上可以看出，比如从小到大排列，越往后，如果出现较小的数， j 就需要移动更多次。另外，如果数据几乎从小到大已排好，那么插入排序就会很快，反之就会很慢，所以他的性能并不稳定。