//插入排序：每次将遍历到的元素插入前面合适的位置
//复杂度：时间O(n2) 空间O(1)
//交换次数O(n2)
//稳定性:稳定
function insertSort(arr){
    let tmp;
    for (let i=0;i<arr.length;i++){
        tmp=arr[i]//当前遍历到的元素
        //插入到合适的位置
        for (let j=i;j>0;j--){
            if (arr[j]<arr[j-1]){
                arr[j]=arr[j-1]
                arr[j-1]=tmp
            }
        }
    }
    return arr
}


console.log(insertSort([5, 4, 3, 2, 1]));