常見的排序算法----直接插入排序（插入排序類，JavaScript實作）

思想

在已排好序中的序列中插入下一個待插入的元素，一般情況下初始時把第一個元素當成已排好序。

1. 從第一個元素開始，該元素可以認為已經被排序
2. 取出下一個元素，在已經排序的元素序列中從後向前掃描
3. 如果已排序好的元素大于新元素，将該元素移到下一位置
4. 重複步驟3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到合适位置中
6. 重複步驟2

function insertionSort(arr) {
    for(var i = 1; i < arr.length; i++) {
        var temp = arr[i];
        if(arr[i] < arr[i-1]) {
            for(var j = i; j > 0 && arr[j-1] > temp; j--) {
                arr[j] = arr[j-1];
            }
            arr[j] = temp;
        }
    }
}
           

複雜度分析

最好的情況：本身已經有序，則為O(n)

最壞的情況：逆序，O(n^2)

平均：O(n^2)

同樣是O(n^2)，直接插入排序比冒泡和簡單選擇排序性能要好一些

直接插入排序是一個穩定的排序

思路參考視訊：https://www.bilibili.com/video/av38482361?from=search&seid=14007900389603348577