插入排序的思想比冒泡、选择要复杂，效率也比前两者更高。插入排序算法中运用了分治、逆向冒泡等思想，假设i之前的都是排好序的，i之后的都是待比较并排序的，然后逐次逆向向前比较，若小于前值，则将前值循环依次后移（等于该值向前冒泡，但减少了交换次数），最后在合适的位置插入用来比较的值。采用两层循环，第一层循环从第一个开始逐个向后检查；第二层循环则比较并插入。
数组仍采用随机数生成。
1 import ‘dart:math‘ show Random; 2 3 void main() { 4 final seed = 100, rnd = Random(), length = 100; 5 var list = 6 List<int>.generate(length, (i) => rnd.nextInt(seed), growable: false); 7 print(list); 8 print(‘---------------------‘); 9 insertSort(list); 10 print(list); 11 } 12 13 void insertSort(List<int> a) { 14 for (var i = 1; i < a.length; i++) { 15 int j, t = a[i]; 16 for (j = i - 1; j >= 0 && t < a[j]; j--) { 17 a[j + 1] = a[j]; 18 } 19 if (j < i - 1) a[j + 1] = t; 20 } 21 }
原文：https://www.cnblogs.com/outerspace/p/10252356.html