-
國家級
全民數字素養與技能培訓基地 -
河南省
第一批產教融合型企業建設培育單位 -
鄭州市
數字技能人才（碼農）培養評價聯盟
插入排序是冒泡排序的優化，是一種直觀的簡單排序算法。它的實現原理是，通過構建有序數組元素的存儲，對于未排序的數組元素，在已排序的數組中從最后一個元素向第一個元素遍歷，找到相應位置并插入。其中，待排序數組的第1個元素會被看作是一個有序的數組，從第2個至最后一個元素會被看作是一個無序數組。如按照從小到大的順序完成插入排序，如圖3-10所示。
圖3-10插入排序從圖3-10可以看出，插入排序比較的次數與無序數組的長度相等，每次無序數組元素與有序數組中的所有元素進行比較，比較后找到對應位置插入，最后即可得到一個有序數組。了解插入排序實現的原理后，下面使用JavaScript實現插入排序。具體如例3-5所示。
【例3-5】demo05.html
< script >
var arr = [89, 56, 100, 21, 87, 45, 1, 888]; // 待排序數組
console.log('待排序數組：' + arr);
// 按照從小到大的順序排列5for (vari = 1; i < arr.length; ++i) {// 遍歷無序數組下標
for (var j = i; j > 0; --j) { // 遍歷并比較一個無序數組元素與所有有序數組元素
if (arr[j - 1] > arr[j]) {
[arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
}
}
}
// 輸出從小到大排序后的數組
console.log('排序后的數組：' + arr);
</script>在上述代碼中，我們假設待查找的數組arr的第1個元素是一個按從小到大排列的有序數組，arr剩余的元素為無序數組。然后通過第5~11行代碼完成插入排序。其中，第7~9行代碼用于無序數組元素與有序數組中的元素進行比較，若無序元素arr[j]小于有序數組中的元素，則進行插入。效果如圖3-11所示。
圖3-11插入排序法
