插入排序算法及其优化(Rust)

2019-04-03  本文已影响0人  平仄_pingze

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

第一版:

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

上一篇下一篇

猜你喜欢

热点阅读