JavaScript插入排序算法原理與實(shí)現(xiàn)方法示例

本文實(shí)例講述了JavaScript插入排序算法原理與實(shí)現(xiàn)方法。分享給大家供大家參考，具體如下：

一、插入排序簡介：

想象我們斗地主，摸排階段，手里的牌都按照從小到大排序。如果每摸一張牌，我們就把他插入合適的位置，使得它比后面位置的牌小，比前面位置的牌大或者相等。

類似這樣的一種排序方法就是插入排序：

在一個(gè)數(shù)組a中，我們要實(shí)現(xiàn)升序排序，假設(shè)我們前面已經(jīng)對a[0]到a[k]排好序，現(xiàn)在需要將a[k+1]的值放入合適的位置。

（為簡便，此處不討論k的取值范圍，只是用它代表數(shù)組的某個(gè)位置）

1、首先，我們將a[k+1]的值與a[k]比較，如果小于a[k]就交換兩者的值，相等或者大于都不需要交換。假設(shè)交換了，那么現(xiàn)在a[k]存放的是原先a[k+1]的值，新的a[k]的值有可能比前面位置的值小，故又需要再次對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]。或者a[k+1]的值比前面的值都小，一步步交換之后a[0]存放了原先a[k+1]的值，那么也結(jié)束。現(xiàn)在a[0]到a[k+1]是一個(gè)有序數(shù)組。

2、對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));

說明：

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)闆]有實(shí)現(xiàn)位置的移動(dòng)。

上述代碼使用在線HTML/CSS/JavaScript代碼運(yùn)行工具h(yuǎn)ttp://tools.jb51.net/code/HtmlJsRun測試運(yùn)行結(jié)果如下：

PS：這里再為大家推薦一款關(guān)于排序的演示工具供大家參考：

在線動(dòng)畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具：
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é)》

希望本文所述對大家JavaScript程序設(shè)計(jì)有所幫助。

聲明：本網(wǎng)頁內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問題請及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com