插入排序是冒泡排序的優(yōu)化,是一種直觀的簡單排序算法。它的實(shí)現(xiàn)原理是,通過構(gòu)建有序數(shù)組元素的存儲,對于未排序的數(shù)組元素,在已排序的數(shù)組中從最后一個(gè)元素向第一個(gè)元素遍歷,找到相應(yīng)位置并插入。其中,待排序數(shù)組的第1個(gè)元素會被看作是一個(gè)有序的數(shù)組,從第2個(gè)至最后一個(gè)元素會被看作是一個(gè)無序數(shù)組。如按照從小到大的順序完成插入排序,如圖3-10所示。
圖3-10插入排序從圖3-10可以看出,插入排序比較的次數(shù)與無序數(shù)組的長度相等,每次無序數(shù)組元素與有序數(shù)組中的所有元素進(jìn)行比較,比較后找到對應(yīng)位置插入,最后即可得到一個(gè)有序數(shù)組。了解插入排序?qū)崿F(xiàn)的原理后,下面使用JavaScript實(shí)現(xiàn)插入排序。具體如例3-5所示。
【例3-5】demo05.html
????var?arr?=?[89,?56,?100,?21,?87,?45,?1,?888];?//?待排序數(shù)組console.log('待排序數(shù)組:'?+?arr);//?按照從小到大的順序排列5for?(vari?=?1;?i??0;?--j)?{?//?遍歷并比較一個(gè)無序數(shù)組元素與所有有序數(shù)組元素????if?(arr[j?-?1]?>?arr[j])?{????????[arr[j?-?1],?arr[j]]?=?[arr[j],?arr[j?-?1]];????}}}//?輸出從小到大排序后的數(shù)組console.log('排序后的數(shù)組:'?+?arr);?
在上述代碼中,我們假設(shè)待查找的數(shù)組arr的第1個(gè)元素是一個(gè)按從小到大排列的有序數(shù)組,arr剩余的元素為無序數(shù)組。然后通過第5~11行代碼完成插入排序。其中,第7~9行代碼用于無序數(shù)組元素與有序數(shù)組中的元素進(jìn)行比較,若無序元素arr[j]小于有序數(shù)組中的元素,則進(jìn)行插入。效果如圖3-11所示。
Copyright ? 2013-2021 河南云和數(shù)據(jù)信息技術(shù)有限公司 豫ICP備14003305號 ISP經(jīng)營許可證:豫B-20160281