介紹
前面介紹的冒泡排序和快速排序屬于排序算法中的交換排序拌屏。今天介紹的直接插入排序則屬于插入排序荆残，算法核心是從待排序數(shù)據(jù)中對比后加入有序數(shù)據(jù)直到所有數(shù)據(jù)都在待排序數(shù)據(jù)芽唇。算法邏輯（升序?yàn)槔?br>
1.以第一個(gè)數(shù)為第一輪的有序數(shù)組弛车；
2.將第二個(gè)數(shù)以第一個(gè)數(shù)對比，大的放在后面滨砍，小的放前面往湿，組成第2輪的有序數(shù)組；
3.以此類推惋戏，第n個(gè)數(shù)與第n-1輪的有序數(shù)組中的數(shù)據(jù)對比领追，遍歷第n輪的有序數(shù)組，知道找到大于第n個(gè)數(shù)據(jù)的數(shù)响逢，插入到這個(gè)數(shù)的前面蔓腐；直到待排序數(shù)組為空；
直接插入排序
例子
假設(shè)有一個(gè)待排序數(shù)組[77, 6, 37, 96, 34, 6, 14], js實(shí)現(xiàn)如下(升序)：
function sort(arr){
let result = [arr[0]];
for(let i = 1; i < arr.length; i++ ){
for(let j = 0; j < result.length; j++){
// 當(dāng)待排序數(shù)小于排序數(shù)組的某個(gè)值時(shí)龄句，插到這個(gè)數(shù)前面
if(arr[i] <= result[j]){
result.splice(j, 0, arr[i]);
break;
// 對比到有序數(shù)組的最后一個(gè)數(shù)據(jù)時(shí)扔沒有小于的則直接放到后面
}else if(j === result.length - 1){
result.push(arr[i]);
break;
}
}
}
return result;
}
sort([77, 6, 37, 96, 34, 6, 14]); // =>[6, 6, 14, 34, 37, 77, 96]
時(shí)間復(fù)雜度
遍歷次數(shù)的計(jì)算與冒泡排序類似：n-1 + n-2 + … + 2 + 1 = n * (n-1) / 2 = 0.5 * n ^ 2 - 0.5 * n，所以時(shí)間復(fù)雜度為O(n^2)散罕。
感謝閱讀分歇！歡迎關(guān)注！持續(xù)更新中...
