js算法：對 插入排序 的了解

1，算法簡介

插入排序的工作原理就是将未排序資料，對已排序資料序列從後向前掃描，找到對應的位置并插入。插入排序通常采用占位的形式，空間複雜度為O(1),是以，在從後向前掃描的過程中，需要反複的把已排序的元素逐漸向後挪位，為新插入元素提供插入的位置。

2，算法描述

1）從第一個元素開始，該元素可以被認為已經被排序

2）取出下一個元素，在已經排好序的序列中從後往前掃描

3）直到找到小于或者等于該元素的位置

4）将該位置後面的所有已排序的元素從後往前依次移一位

5)将該元素插入到該位置

6)重複步驟2~5

了解步驟看注釋

//插入排序 O(n*n)
function MySort3(arr) {
	var len = arr.length;
	//此處i = 1，從第二個元素開始比對，預設第一個元素已經排序，此處跟下面while循環的 j>=0 保留一個就行，另一個沒有意義
	for (var i = 1; i < len; i++) {
		var current = arr[i];//記錄目前需要插入排序的元素，避免下面while循環被覆寫
		// 以arr[i]為分界線，前面的是已經排序的，後面是未排序的
		var j = i - 1; //最開始while循環之前 j 是預設已排序的元素中的 最後一個的索引，此處每次for循環會重新定義j
		while (j >= 0 && arr[j] > current) { //在已排序好的隊列中從後向前比對
			arr[j + 1] = arr[j]; //已排序的元素大于新元素，将該元素移到一下個位置
			j--;
		}
		// 直到while循環不滿足條件才會執行
		arr[j + 1] = current;
	}
	return arr
}
let arr3 = [5, 7, 9, 3, 4, 5, 6, 1, 2, 3, 7, 5, 4, 1, 2]
console.log('插入排序：', MySort3(arr3))