插入排序

简介

插入排序是，对于元素nums[i]，在它之前[0..i]已排序的序列中找到它应在的位置 j插入，并将[j..i)之间的元素后移一位。

效率

• 时间复杂度：
• 空间复杂度：
• 稳定性：稳定

  实现

  pub fn insertion_sort(mut nums: Vec<i32>) -> Vec<i32> {
    for i in 1..nums.len() {
        let curr = nums[i];
        for j in (0..i).rev() {
            if nums[j] > curr {
                nums[j + 1] = nums[j];
                if j == 0 {
                    nums[j] = curr;
                }
            } else {
                nums[j + 1] = curr;
                break;
            }
        }
    }
    nums
  }