插入排序算法的原理是，通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
开始时，认为第一个元素自身是一个有序序列。
第一版：
pub fn insertion_sort(v: &mut [i32]) {
let len = v.len();
for i in 1..len {
for j in 0..i {
if v[i] < v[j] {
let temp = v[i];
let mut k = i;
while k > j {
v[k] = v[k-1];
k-=1;
}
v[j] = temp;
break;
}
}
}
}
其中，i是无序部分需要插入到有序序列的元素索引；j是对有序序列扫描的索引。
对从第二个元素开始的每个元素，都对前面的所有有序元素进行正序遍历，直到找到一个比它大的，就将自己插入这个位置。
插入的方式是，这个位置和后面的有序序列内的元素，按倒序依次向后移位；自己填入这个位置。
可以看到，实现使用了3重循环，4层嵌套。
优化的实现：
pub fn insertion_sort(v: &mut [i32]) {
let len = v.len();
for i in 1..len {
let temp = v[i];
let mut j = i;
while j > 0 && temp < v[j-1] {
v[j] = v[j-1];
j -= 1;
}
v[j] = temp;
}
}
按照上述逻辑，正序遍历只在找到比自己大的有序元素时，才进行操作；这可以转换为，倒序遍历，只要有序元素比自己小，就立即使之向右移位，（比自己大则不操作）；最后将自己填入最后一个比自己小的元素的原位置。
如此，只需使用2重循环，2重嵌套。
（优化点在于：1. 对有序元素遍历同时进行移位；2. 将大小比较作为循环条件）
