插入排序算法及其优化(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. 将大小比较作为循环条件)