插入排序
本文将介绍基础的插入排序算法
引言
假设我们在打扑克牌,当你抽到一张新的牌时,你会考虑把这张牌插入到哪个位置,按照我的习惯我会把更小的牌放在左边,更大的牌放在右边,就像下面这张图一样:
如果在牌局的一开始就按这个规则插牌,那么每当摸到新的牌后,只需要在现有手牌中找出一个合适的位置把新的牌插入进去就行了,这样一次只需要改变一张牌(新插入的那张)的位置,其余牌的相对位置不变。
插入排序算法描述
以下是stackoverflow上找到的一个动图:
rust语言实现
insertion_sort.rs
代码解释
当前使用的插入排序算法是原地排序,所以arr是一个可变引用,insertion_sort方法不用返回值,因为arr自身会被修改,当然如果想改为无副作用的形式也很简单
为什么要把cursor这个元素单独提取出来?因为当寻找位置插入时,未排序部分整体会右移动一格,需要提取出来以释放位置
下面的cfg(test), mod tests之类的代码是干嘛用的?用这种方式描述测试用例
Last updated