Dart 算法篇 | 插入排序
1.源码中的 Sort 排序
在 sky_engine/lib/internal/sort.dart
中有一个 Sort
类,其中 sortRange
方法可以进行排序。可以看出 sortRange
方法是对 List 索引范围区间进行排序。
1---->[sky_engine/lib/internal/sort.dart]----
2static void sortRange(List 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(
4 List 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(
2 List 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(
9 List 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
就需要移动更多次。另外,如果数据几乎从小到大已排好,那么插入排序就会很快,反之就会很慢,所以他的性能并不稳定。