基本算法-插入排序

伪代码

for j = 2 to A.length
key = A[j]
i = j - 1
while i>0 and A[i] > key
A[i+1] = A[i]
i = i - 1
A[i+1] = key

JS基本实现

var testArr = [0,3,3,8,2,9,1,7,1,34,12]
for(var i=1;i<testArr.length;i++){
	var key = testArr[i]
	j = i -1
	while(j>=0 && testArr[j] > key){
		testArr[j+1] = testArr[j]
		j = j - 1
		testArr[j+1] = key
	}
}
console.log(testArr)

代码解释

从第二个元素开始，依次与之前元素相比较，若前面元素较大，则交换位置

封装

/**
 * [insertSort 插入排序]
 * @Author   etoile
 * @DateTime 2017-03-12T11:09:27+0800
 * @param    {[type]}                 arr [排序元素]
 * @param    {[type]}                 dir [排序方向 正数：从小到大 负数：从大到小]
 * @return   {[type]}                     [description]
 */
function insertSort(arr, dir) {
    for (var i = 1; i < arr.length; i++) {
        var key = arr[i]
        var j = i - 1
        while (j >= 0 && (arr[j] - key)*dir > 0) {
            arr[j + 1] = arr[j]
            j = j - 1
            arr[j + 1] = key
        }


    }
    return arr;
}