当前位置:   article > 正文

【算法】插入排序

【算法】插入排序

一、算法图示

在这里插入图片描述

二、算法思想

  • 图示以7 1 5 4 1 8 11为例进行;
  • 开始设定第一个数7为有序数,因此从第二个数1开始进行;
  • 第一轮开始:1向前找比它大的数,发现了7,进行交换;
  • 第一轮结束后,前两个数已经是排序好的数;
  • 第二轮开始:第3个数5向前找比它大的数,发现了7,进行交换;
  • 第三轮开始:第四个数4向前找比它大的数,发现了7,进行交换;继续向前找,与5对比,还是比它大,继续交换;再向前之后就比它小了,结束;
  • 其它的以此类型,由于前面标红的部分是已经排序好的有序数列,因此一旦发现不满足大小关系就可以提前结束当前循环;

三、代码实现

pub fn insert_sort<T: PartialOrd>(src: &mut Vec<T>){
   

    let length = src.len();

    for i in 1..length {
   
        for j in (1..=i).rev(){
   
            if src[j] < src[j-1] {
   
                src.swap(j, j-1);
            }
            else {
   
                break;
            }
        }
    }
}

#[cfg(test)]
mod tests{
   
 	……
    #[test]
    fn insert_sort_test(){
   
        let mut num = vec![ 7, 1, 5, 4, 1, 8, 11];
        select_sort(&mut num);
        
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号