本文除了會(huì)帶大家了解一些Array.prototypr.sort()方法(后面簡(jiǎn)寫為sort()方法)的基本定義和用法之外洪己，還會(huì)探討一下sort()方法到底是使用的什么排序算法务冕。簡(jiǎn)單度娘了一下拇囊，網(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)定的客扎。
語(yǔ)法
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或元素末定義）
實(shí)例
//例1.字母排序
var a = new Array("banna","watermelon","orange","apple");
s.sort();
console.log(a) //輸出 ["apple", "banna", "orange", "watermelon"]
//沒什么好說的筒饰，比較函數(shù)缺省缴啡，按照字母順序升序排序 a<b<o<w
//例2.轉(zhuǎn)化為字母排序
var a=[11,2,44,3,5,6];
a.sort();
console.log(a) // [11, 2, 3, 44, 5, 6]
//說明第一條，數(shù)字轉(zhuǎn)為字符串瓷们，"11"<"2"<"3"<"44"<"5"<"6"
//例3.數(shù)字排序
var a=[11,2,44,3,5,6];
a.sort(function(a,b){
return a-b; //升序——當(dāng)a<b時(shí)业栅，a-b返回一個(gè)小于0的值。根據(jù)說明2-a谬晕，a會(huì)在b的前面碘裕，則實(shí)現(xiàn)了升序排序。反之如果想實(shí)現(xiàn)降序排序攒钳，return b-a即可帮孔。
});
console.log(a) //輸出 [2, 3, 5, 6, 11, 44]
//例3.隨機(jī)排序
var a=[11,2,44,3,5,6];
a.sort(function(a,b){
return Math.random()>.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)評(píng)論區(qū)大神的提醒檐迟，EMCAScript并沒有定義sort()方法使用的排序算法，各個(gè)瀏覽器實(shí)現(xiàn)的方式并不相同码耐。以上的結(jié)論我只在chrome和fireFox中存在追迟。以上結(jié)論在chrome和fireFox也并不完全正確，當(dāng)數(shù)組長(zhǎng)度過長(zhǎng)時(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 a<b?-1:a===b?0:1;
}
Array.prototype._sort=function(f){
/**
* 如未傳入實(shí)參
* 或傳入的實(shí)參不是函數(shù)
* 使用默認(rèn)的排序函數(shù) （按字符順序）
*/
var f=f&&typeof(f)=="function"?f:Array.prototype._sort.f,
len=this.length,
i=0,
t;
/**
* 這個(gè)循環(huán)開始排序
* Array.sort()使用的是一種冒泡各插入結(jié)合的排序方法
*
*/
for(i=0,t=undefined;i<len-1;i++){
if(f(this[i],this[i+1])>0){ //大于零則需要交接位置
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)開始之前添加這樣一段窟哺。
//這個(gè)循環(huán)把所有數(shù)組undefined的元素和數(shù)組最后一個(gè)不是undefined的元素替換
//不同瀏覽器對(duì)undefined處理方式不同泻轰，這里模仿chrome的處理方式
for(;i<len;i++){
if(this[i]===undefined){ //
/**
* while找到最后一個(gè)(len-1)不是undefined的元素的下標(biāo)
* 同時(shí)更新需要排序的元素個(gè)數(shù)(len)
* 那些個(gè)undefined就不鳥它了
* 下標(biāo)小于i的元素已經(jīng)檢查替換完成了，不需要再重復(fù)一次且轨。所以添加一個(gè)len>=i的條件
*/
while(this[len-1]===undefined&&len>=i){
len--;
}
/**
* 如果len等于i
* 就表示下標(biāo)不小于i的元素都是undefined了
* 可以不用繼續(xù)遍歷了
*/
if(len===i) break;
/**
* 使用t將最后一個(gè)不是undefined的元素保存起來
* i in this 是判斷這個(gè)元素是不存在浮声，還是值是undefined
* 數(shù)組中一個(gè)不存在的元素，也會(huì)返回undefined(稀疏數(shù)組)
* 這兩者還是有區(qū)別的
* 如果不存在i in this會(huì)返回 false
*/
t=this[len-1];
if(i in this)
this[len-1]=undefined; //元素值為undefined旋奢，直接將要替換元素值設(shè)為undefined
else
delete this[len-1]; //元素不存在泳挥，通過刪除將要替換的元素設(shè)置為不存在，
this[i]=t; //替換undefined元素
//又塞了一個(gè)undefinef到后面至朗，所以要排序的元素又少了一個(gè)屉符，再減減一下
len--;
}
}
到這里是真結(jié)束了，謝謝大家锹引！如何有什么我說錯(cuò)了或者沒說明白的地方矗钟，歡迎大家留言一起討論，大家一起學(xué)習(xí)嫌变，共同進(jìn)步么真仲。
