資訊專欄INFORMATION COLUMN
摘要：本文除了會(huì)帶大家了解一些方法后面簡寫為方法的基本定義和用法之外，還會(huì)探討一下方法到底是使用的什么排序算法。下面我們來看看方法到底是如何排序的。
??本文除了會(huì)帶大家了解一些Array.prototypr.sort()方法(后面簡寫為sort()方法)的基本定義和用法之外，還會(huì)探討一下sort()方法到底是使用的什么排序算法。簡單度娘了一下，網(wǎng)上的那些sort()方法詳解文章，大多只說了sort()方法的用法。還有說sort()方法是使用冒泡法做的排序，這是錯(cuò)誤的。下面，我們發(fā)車！
sort()方法??先來看看sort()方法的一些基礎(chǔ)知識(shí)。已經(jīng)了解sort()方法的童鞋可以直接跳過這部分。
sort() 方法在適當(dāng)?shù)奈恢脤?duì)數(shù)組的元素進(jìn)行排序，并返回?cái)?shù)組。 sort 排序不一定是穩(wěn)定的。
arr.sort()
arr.sort(compareFunction)
1.如果沒有指明 compareFunction ，那么元素會(huì)按照轉(zhuǎn)換為的字符串的諸個(gè)字符的Unicode位點(diǎn)進(jìn)行排序。
2.如果指明了 compareFunction ，那么數(shù)組會(huì)按照調(diào)用該函數(shù)的返回值排序。即 a 和 b 是兩個(gè)將要被比較的元素：
?? a.如果 compareFunction(a, b) 小于 0 ，那么 a 會(huì)被排列到 b 之前；
?? b.如果 compareFunction(a, b) 等于 0 ， a 和 b 的相對(duì)位置不變。(ECMAScript 標(biāo)準(zhǔn)并不保證這一行為，而且也不是所有瀏覽器都會(huì)遵守,例如 Mozilla 在 2003 年之前的版本）；
?? c.如果 compareFunction(a, b) 大于 0 ， b 會(huì)被排列到 a 之前。
??d. compareFunction(a, b)必須總是對(duì)相同的輸入返回相同的比較結(jié)果，否則排序的結(jié)果將是不確定的。(利用這一特性，可實(shí)現(xiàn)隨機(jī)排序)
3.如果數(shù)組包含undefined元素（元素值為undefined或元素末定義）
以上90%引用自MDN
//例1.字母排序
var a = new Array("banna","watermelon","orange","apple");
s.sort();
console.log(a) //輸出 ["apple", "banna", "orange", "watermelon"]
//沒什么好說的，比較函數(shù)缺省，按照字母順序升序排序 a.5?-1:1; //根據(jù)說明2-c特性，實(shí)現(xiàn)隨機(jī)排序
});
console.log(a) //每次運(yùn)行的輸出都不同
??以上是sort()方法的一些基本用法,MDN里還有更多的用法。下面我們來看看sort()方法到底是如何排序的。
sort()方法如何實(shí)現(xiàn)排序??怎么查看sort()方法是如果實(shí)現(xiàn)排序的呢？我們可以在比較函數(shù)里把a(bǔ),b及數(shù)組輸出一下，看看是否能夠看出使用的排序算法。
var arr=[1, 8, 3, 5, -1];
function compare(a,b){
console.log(a,b,arr);
return a-b;
}
arr.sort(compare);
/**
控制臺(tái)輸出
1 8 [1, 8, 3, 5, -1]
8 3 [1, 8, 3, 5, -1]
1 3 [1, 8, 8, 5, -1]
8 5 [1, 3, 8, 5, -1]
3 5 [1, 3, 8, 8, -1]
8 -1 [1, 3, 5, 8, -1]
5 -1 [1, 3, 5, 8, 8]
3 -1 [1, 3, 5, 5, 8]
1 -1 [1, 3, 3, 5, 8]
[-1,1, 3, 5, 8]
*/
??不知道同學(xué)們有沒有看出什么端倪。反正我一開始是什么都沒有發(fā)現(xiàn)，那就分析分析咯。
??第一次1和8比較，1<8，不需要調(diào)整位置。
??第二次8和3比較，8>3，需要調(diào)整位置。但是這里沒有交換位置，僅僅是8覆蓋了3位置。這里就可以推斷出不是單純的使用了冒泡算法。
??第三是1和3比較，1<3，3替換了8的位置。什么鬼，幾個(gè)意思？？？看到這里我也是表示不懂呀。那就繼續(xù)往下看咯。
??第四是8和5比較，8>5，又僅僅是覆蓋，沒有交換位置。還是不懂，繼續(xù)往下！
??第五是3和5比較，3<5，5替換了8的位置，不懂，繼續(xù)往下！
??第六是8和-1比較，8>-1， 還僅僅是覆蓋，繼續(xù)往下！
??第七、八、九次，-1依次和5，3，1做了比較，并且5，3，1都移動(dòng)了一次位置。等等，這怎么和插入排序法有點(diǎn)相似。
??再試試一下
var arr=[1, 8, 9, 5, 2]; arr.sort(compare); /** 控制臺(tái)輸出 1 8 [1, 8, 9, 5, 2] 8 9 [1, 8, 9, 5, 2] 9 5 [1, 8, 9, 5, 2] 8 5 [1, 8, 9, 9, 2] 1 5 [1, 8, 8, 9, 2] 9 2 [1, 5, 8, 9, 2] 8 2 [1, 5, 8, 9, 9] 5 2 [1, 5, 8, 8, 9] 1 2 [1, 5, 5, 8, 9] [1, 2, 5, 8, 9] */
??沒跑了，這就是插入法。再捋捋，第一次冒泡完之后，前兩位肯是有序的。第二次比較，如果發(fā)生位變化，a先向后移動(dòng)一位，b沒有直接前移，而是通過插入法找到正確的位置插入，此時(shí)前三位有序。如果沒有發(fā)生位置變化，說明此時(shí)前三位已經(jīng)有序，繼續(xù)拿有序的最后一位和之后的一位比較。如此循環(huán)，直至整個(gè)數(shù)組有序。
??到這里，我們得出了結(jié)論：sort()方法是使用的冒泡和插入兩種方式結(jié)合進(jìn)行排序的。 如果對(duì)排序不熟悉的同學(xué)，可以看看——《十大經(jīng)典排序算法》
??經(jīng)一位大神的提醒，EMCAScript并沒有定義sort()方法使用的排序算法，各個(gè)瀏覽器實(shí)現(xiàn)的方式并不相同。以上的結(jié)論我只在chrome和fireFox中存在。以上結(jié)論在chrome和fireFox也并不完全正確，當(dāng)數(shù)組長度過長時(shí)，就不在是使用冒泡和插入兩種方式結(jié)合進(jìn)行排序了，而是使用一種我不了解方法。先修改錯(cuò)誤的結(jié)論。等我弄清楚那種我不了解的方法，再來更新_srot()方法。
??童鞋你似不似以為到這里就完了，文章就完美結(jié)束了？當(dāng)然不似!!!接下來,閑著沒事我們模仿sort(),實(shí)現(xiàn)一個(gè)和sort()方法功能一樣的自定義方法玩玩呀。
實(shí)現(xiàn)一個(gè)和sort()方法相似的_sort()方法??這里不多說，直接上代碼。然后看注釋
Array.prototype._sort.f=function(a,b){ //設(shè)置默認(rèn)按照Unicode位點(diǎn)進(jìn)行排序
a+="",b+="";
return a0){ //大于零則需要交接位置
t=this[i+1],this[i+1]=this[i];
}
/**
* 如果t值是unfeined，
* 則當(dāng)前的這次騎比較沒有發(fā)生位置變化
* 也就不需要使用插入法了
*/
if(t){
//使用插入法找到正確的插入位置，上面排序算法還有優(yōu)化插入法排序的方法
for(var j=i-1;j>=0;j--){
if(f(this[j],t)>0){//如果當(dāng)前元素大于t,則當(dāng)前元素后移一位
this[j+1]=this[j];
}else{//否則表示找到插入點(diǎn)了，插入t,并退出循環(huán)
this[j+1]=t;
t=undefined;//將t設(shè)為undefined，防止冒泡未發(fā)生替換就進(jìn)入插入法排序
break;
}
}
}
}
return this; //返回排序后的新數(shù)組
}
??到這里就完了？？？No!No!No!雖然我們實(shí)現(xiàn)了_sort()方法，但是還有一個(gè)不完美的地方。說明第三點(diǎn)說了對(duì)undefined的處理規(guī)則，我們還沒有對(duì)unfined進(jìn)行任何處理呢。還需要在上面的排序循環(huán)開始之前添加這樣一段。
