插入排序

• 全称 Insertion sort

• 特点

  • 稳定
  • 时间复杂度
    • 最优 O(n), 完全有序时
    • 最坏和平均 O(n2)

• 原理

  • 外层 1 ~ n-1 循环，每次记录当前值
  • 内层 向前面区间(0, i)从后往前扫描过去，比当前值大的就让它占据当前自己的位置
    • 不断继续往前，直到尽头或者找到小于等于当前值的
    • 最后把当前值插入到区间的扫描停止位置后一个
    • 注意
      • 从第1个元素循环开始，每一个元素都有机会向左侧发起冲锋
      • 不可能出现 6 2 4 这种情况，就是说不可能4被更小2拦住了但却应该到更大的6之前
      • 因为2一定会冲锋到6的左侧，形成2 6 4 这种局面，也就是说扫描过的左侧区间必然是有序的，要做的只是找到当前值应该在的位置

let insertionSort = (arr) => {
    const len = arr.length;
    for(let i = 1; i < len; ++i){
        const key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

let shuffle = (arr) => {
    let n = arr.length;
    while (n > 0) {
        const random = (Math.random() * n--) >>> 0;
        [arr[random], arr[n]] = [arr[n], arr[random]];
    }
    return arr;
}

(() => {
    let testArr = [5, 7, 3, 4, 2, 6, 1];
    shuffle(testArr);
    insertionSort(testArr);
    console.log(testArr);
})()

#include <iostream>
#include <vector>
#include<bits/stdc++.h>
using namespace std;

void insertionSort(vector<int>& nums) {
    int len = nums.size();
    for(int i = 1; i < len; ++i){
        int key = nums[i];
        int j = i - 1;
        while(j >= 0 && nums[j] > key){
            nums[j + 1] = nums[j];
            --j;
        }
        nums[j + 1] = key;
    }
};

void shuffle(vector<int>& arr) {
    int n = arr.size();
    srand(time(NULL));
    while (n--) {
        const int random = rand() % arr.size();
        swap(arr[n], arr[random]);
    }
}

int main() {
    vector<int> testArr = {5, 7, 3, 4, 2, 6, 1};
    shuffle(testArr);
    insertionSort(testArr);
    for(auto e: testArr) cout<<e<<endl;
    return 0;
}