插入排序算法及其优化（Rust）

插入排序算法的原理是，通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
开始时，认为第一个元素自身是一个有序序列。

第一版：

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. 将大小比较作为循环条件）