插入排序

本文将介绍基础的插入排序算法

引言

假设我们在打扑克牌,当你抽到一张新的牌时,你会考虑把这张牌插入到哪个位置,按照我的习惯我会把更小的牌放在左边,更大的牌放在右边,就像下面这张图一样:

如果在牌局的一开始就按这个规则插牌,那么每当摸到新的牌后,只需要在现有手牌中找出一个合适的位置把新的牌插入进去就行了,这样一次只需要改变一张牌(新插入的那张)的位置,其余牌的相对位置不变。

插入排序算法描述

以下是stackoverflow上找到的一个动图:

rust语言实现

insertion_sort.rs
fn insertion_sort(arr: &mut Vec<usize>) { // 1. arr是一个可变引用
    let len = arr.len();
    for i in 0..len {                     // 2. 遍历当前数组
        let mut pos = i;                  // 3. pos 是当前位置,pos之前的部分有序,之后的无序
        let cursor = arr[i];              // 4. cursor是当前待排序的元素
        while pos > 0 && arr[pos - 1] > cursor { // 5. 寻找一个合适的位置放入cursor(把cursor和它之前的每个元素做比较
            arr[pos] = arr[pos - 1];             // 如果cursor更小就把对应元素往后挪一格)
            pos = pos - 1;
        }
        arr[pos] = cursor;                // 6. 最后空出的格子放置待排序的元素
    }
}

#[cfg(test)]
mod tests {
    #[test]
    fn test_insertion_sort() {
        let mut arr = vec![4, 3, 2, 1];
        insertion_sort(&mut arr);
        assert_eq!(vec![1, 2, 3, 4], arr);
    }
}

代码解释

  1. 当前使用的插入排序算法是原地排序,所以arr是一个可变引用,insertion_sort方法不用返回值,因为arr自身会被修改,当然如果想改为无副作用的形式也很简单

  2. 为什么要把cursor这个元素单独提取出来?因为当寻找位置插入时,未排序部分整体会右移动一格,需要提取出来以释放位置

  3. 下面的cfg(test), mod tests之类的代码是干嘛用的?用这种方式描述测试用例

Last updated