教育行業(yè)A股IPO第一股(股票代碼 003032)

全國咨詢/投訴熱線:400-618-4000

插入排序的實現(xiàn)原理是什么?怎樣實現(xiàn)插入排序

更新時間:2022年03月25日15時37分 來源:傳智教育 瀏覽次數(shù):

插入排序是冒泡排序的優(yōu)化,是一種直觀的簡單排序算法。它的實現(xiàn)原理是,通過構(gòu)建有序數(shù)組元素的存儲,對于未排序的數(shù)組元素,在已排序的數(shù)組中從最后一個元素向第一個元素遍歷,找到相應(yīng)位置并插入。其中,待排序數(shù)組的第1個元素會被看作是一個有序的數(shù)組,從第2個至最后一個元素會被看作是一個無序數(shù)組。如按照從小到大的順序完成插入排序,如圖3-10所示。

圖3-10插入排序從圖3-10可以看出,插入排序比較的次數(shù)與無序數(shù)組的長度相等,每次無序數(shù)組元素與有序數(shù)組中的所有元素進(jìn)行比較,比較后找到對應(yīng)位置插入,最后即可得到一個有序數(shù)組。了解插入排序?qū)崿F(xiàn)的原理后,下面使用JavaScript實現(xiàn)插入排序。具體如例3-5所示。

【例3-5】demo05.html

< script >
    var arr = [89, 56, 100, 21, 87, 45, 1, 888]; // 待排序數(shù)組
console.log('待排序數(shù)組:' + arr);
// 按照從小到大的順序排列5for (vari = 1; i < arr.length; ++i) {// 遍歷無序數(shù)組下標(biāo)
for (var j = i; j > 0; --j) { // 遍歷并比較一個無序數(shù)組元素與所有有序數(shù)組元素
    if (arr[j - 1] > arr[j]) {
        [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
    }
}
}
// 輸出從小到大排序后的數(shù)組
console.log('排序后的數(shù)組:' + arr); 
</script>

在上述代碼中,我們假設(shè)待查找的數(shù)組arr的第1個元素是一個按從小到大排列的有序數(shù)組,arr剩余的元素為無序數(shù)組。然后通過第5~11行代碼完成插入排序。其中,第7~9行代碼用于無序數(shù)組元素與有序數(shù)組中的元素進(jìn)行比較,若無序元素arr[j]小于有序數(shù)組中的元素,則進(jìn)行插入。效果如圖3-11所示。


圖3-11插入排序法




猜你喜歡:

什么是冒泡排序?手寫一段冒泡排序的代碼

JS如何實現(xiàn)數(shù)組隨機排序?JS數(shù)組隨機排序的3種方法

Hadoop如何實現(xiàn)二次排序?

列表的排序過渡

傳智教育web前端培訓(xùn)課程

0 分享到:
和我們在線交談!