【算法】插入排序

• 一、算法图示
• 二、算法思想
• 三、代码实现
• 四、算法效率分析
• • 4.1 更新运行时长函数
  • 4.2 与选择排序对比
• 五、算法改进
• • 5.1 结论分析
  • 5.2 改进算法图示
  • 5.3 算法说明
  • 5.4 代码实现
  • 5.5 算法效率对比
  • • 1）算法升级前后对比
    • 2）与选择排序对比

一、算法图示

二、算法思想

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

三、代码实现

pub fn insert_sort(src: &mut Vec){
   
    let length = src.len();
    for i in 1..length {
   
        for j in (1..=i).rev(){
   
            if src[j]