JavaScript插入排序算法原理與實(shí)現(xiàn)方法示例
本文實(shí)例講述了JavaScript插入排序算法原理與實(shí)現(xiàn)方法。分享給大家供大家參考,具體如下:
一、插入排序簡(jiǎn)介:
想象我們斗地主,摸排階段,手里的牌都按照從小到大排序。如果每摸一張牌,我們就把他插入合適的位置,使得它比后面位置的牌小,比前面位置的牌大或者相等。
類似這樣的一種排序方法就是插入排序:
在一個(gè)數(shù)組a中,我們要實(shí)現(xiàn)升序排序,假設(shè)我們前面已經(jīng)對(duì)a[0]到a[k]排好序,現(xiàn)在需要將a[k+1]的值放入合適的位置。
(為簡(jiǎn)便,此處不討論k的取值范圍,只是用它代表數(shù)組的某個(gè)位置)
1、首先,我們將a[k+1]的值與a[k]比較,如果小于a[k]就交換兩者的值,相等或者大于都不需要交換。假設(shè)交換了,那么現(xiàn)在a[k]存放的是原先a[k+1]的值,新的a[k]的值有可能比前面位置的值小,故又需要再次對(duì)a[k]與a[k-1]進(jìn)行比較,以此類推。直到發(fā)現(xiàn)某個(gè)位置a[p](p是0到k之間數(shù))的值已經(jīng)不比a[p-1]的值小,比較結(jié)束,a[k+1]的值已經(jīng)放入合適的位置a[p]?;蛘?span style="color: #0000ff">a[k+1]的值比前面的值都小,一步步交換之后a[0]存放了原先a[k+1]的值,那么也結(jié)束?,F(xiàn)在a[0]到a[k+1]是一個(gè)有序數(shù)組。
2、對(duì)a[k+1]之后a[k+2]到a[a.length-1]的每一個(gè)元素都依次進(jìn)行相同操作,最終得到一個(gè)有序數(shù)組。
二、JavaScript實(shí)現(xiàn)插入排序
function insertion_sort(arr) { var temp; for (var i = 1; i < arr.length; i++) { for (var j = i-1; j >=0; j--) { if (arr[j+1]<arr[j]) { temp=arr[j+1]; arr[j+1]=arr[j]; arr[j]=temp; }else if (arr[j+1]>=arr[j]) { break; } } } return arr; } var a=[11,2,3,445,7,32,71,8,94]; console.log(insertion_sort(a)); var b=[94,11]; console.log(insertion_sort(b));
說(shuō)明:
1、一旦發(fā)現(xiàn)arr[j+1]的值不比前面的值小,就可以結(jié)束內(nèi)層循環(huán)了,break
實(shí)現(xiàn)這一功能;
2、內(nèi)層循環(huán)用arr[j+1]的原因:初始時(shí)a[j](即a[i-1])代表a[i]前一個(gè)位置,進(jìn)入循環(huán)后,a[j+1]就表示了a[i]的位置,實(shí)現(xiàn)了a[i]和a[i-1]的第一次比較;隨著j第一次自減,實(shí)際上比較了a[i-1]和a[i-2];依次類推。如果將arr[j+1]改成a[i]是不行的,因?yàn)闆](méi)有實(shí)現(xiàn)位置的移動(dòng)。
上述代碼使用在線HTML/CSS/JavaScript代碼運(yùn)行工具http://tools.jb51.net/code/HtmlJsRun測(cè)試運(yùn)行結(jié)果如下:
PS:這里再為大家推薦一款關(guān)于排序的演示工具供大家參考:
在線動(dòng)畫(huà)演示插入/選擇/冒泡/歸并/希爾/快速排序算法過(guò)程工具:
http://tools.jb51.net/aideddesign/paixu_ys
更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)組操作技巧總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》
希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。
相關(guān)文章
[Bootstrap-插件使用]Jcrop+fileinput組合實(shí)現(xiàn)頭像上傳功能實(shí)例代碼
這篇文章主要介紹了[Bootstrap-插件使用]Jcrop+fileinput組合實(shí)現(xiàn)頭像上傳功能實(shí)例代碼,非常具有實(shí)用價(jià)值,需要的朋友可以參考下。2016-12-12JS實(shí)現(xiàn)跟隨鼠標(biāo)立體翻轉(zhuǎn)圖片的方法
這篇文章主要介紹了JS實(shí)現(xiàn)跟隨鼠標(biāo)立體翻轉(zhuǎn)圖片的方法,涉及javascript操作圖片翻轉(zhuǎn)的相關(guān)技巧,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2015-05-05javascript 實(shí)現(xiàn)動(dòng)態(tài)側(cè)邊欄實(shí)例詳解
這篇文章主要介紹了javascript 實(shí)現(xiàn)動(dòng)態(tài)側(cè)邊欄實(shí)例詳解的相關(guān)資料,并附實(shí)例代碼,幫助大家學(xué)習(xí)理解,需要的朋友可以參考下2016-11-11JavaScript實(shí)現(xiàn)簡(jiǎn)單計(jì)時(shí)器
這篇文章主要為大家詳細(xì)介紹了JavaScript實(shí)現(xiàn)簡(jiǎn)單計(jì)時(shí)器,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-06-06Bootstrap表單簡(jiǎn)單實(shí)現(xiàn)代碼
這篇文章主要為大家詳細(xì)介紹了Bootstrap表單的簡(jiǎn)單實(shí)現(xiàn)代碼,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2017-03-03