摘要：本文除了會帶大家了解一些方法后面簡寫為方法的基本定義和用法之外，還會探討一下方法到底是使用的什么排序算法。下面我們來看看方法到底是如何排序的。

??本文除了會帶大家了解一些Array.prototypr.sort()方法(后面簡寫為sort()方法)的基本定義和用法之外，還會探討一下sort()方法到底是使用的什么排序算法。簡單度娘了一下，網(wǎng)上的那些sort()方法詳解文章，大多只說了sort()方法的用法。還有說sort()方法是使用冒泡法做的排序，這是錯誤的。下面，我們發(fā)車！

??先來看看sort()方法的一些基礎(chǔ)知識。已經(jīng)了解sort()方法的童鞋可以直接跳過這部分。

定義

sort() 方法在適當(dāng)?shù)奈恢脤?shù)組的元素進行排序，并返回數(shù)組。 sort 排序不一定是穩(wěn)定的。

語法

arr.sort()

arr.sort(compareFunction)

說明

1.如果沒有指明 compareFunction ，那么元素會按照轉(zhuǎn)換為的字符串的諸個字符的Unicode位點進行排序。 
2.如果指明了 compareFunction ，那么數(shù)組會按照調(diào)用該函數(shù)的返回值排序。即 a 和 b 是兩個將要被比較的元素：

?? a.如果 compareFunction(a, b) 小于 0 ，那么 a 會被排列到 b 之前；
?? b.如果 compareFunction(a, b) 等于 0 ， a 和 b 的相對位置不變。(ECMAScript 標(biāo)準(zhǔn)并不保證這一行為，而且也不是所有瀏覽器都會遵守,例如 Mozilla 在 2003 年之前的版本）；
?? c.如果 compareFunction(a, b) 大于 0 ， b 會被排列到 a 之前。
??d. compareFunction(a, b)必須總是對相同的輸入返回相同的比較結(jié)果，否則排序的結(jié)果將是不確定的。(利用這一特性，可實現(xiàn)隨機排序)

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特性，實現(xiàn)隨機排序
});
console.log(a) //每次運行的輸出都不同

??以上是sort()方法的一些基本用法,MDN里還有更多的用法。下面我們來看看sort()方法到底是如何排序的。

??怎么查看sort()方法是如果實現(xiàn)排序的呢？我們可以在比較函數(shù)里把a,b及數(shù)組輸出一下，看看是否能夠看出使用的排序算法。

var arr=[1, 8, 3, 5, -1];
function compare(a,b){
    console.log(a,b,arr);
    return a-b;
}
arr.sort(compare);
/**
控制臺輸出
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的位置。什么鬼，幾個意思？？？看到這里我也是表示不懂呀。那就繼續(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都移動了一次位置。等等，這怎么和插入排序法有點相似。

??再試試一下

var arr=[1, 8, 9, 5, 2];
arr.sort(compare);
/**
控制臺輸出
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先向后移動一位，b沒有直接前移，而是通過插入法找到正確的位置插入，此時前三位有序。如果沒有發(fā)生位置變化，說明此時前三位已經(jīng)有序，繼續(xù)拿有序的最后一位和之后的一位比較。如此循環(huán)，直至整個數(shù)組有序。

??到這里，我們得出了結(jié)論：sort()方法是使用的冒泡和插入兩種方式結(jié)合進行排序的。 如果對排序不熟悉的同學(xué)，可以看看——《十大經(jīng)典排序算法》

??經(jīng)一位大神的提醒，EMCAScript并沒有定義sort()方法使用的排序算法，各個瀏覽器實現(xiàn)的方式并不相同。以上的結(jié)論我只在chrome和fireFox中存在。以上結(jié)論在chrome和fireFox也并不完全正確，當(dāng)數(shù)組長度過長時，就不在是使用冒泡和插入兩種方式結(jié)合進行排序了，而是使用一種我不了解方法。先修改錯誤的結(jié)論。等我弄清楚那種我不了解的方法，再來更新_srot()方法。

??童鞋你似不似以為到這里就完了，文章就完美結(jié)束了？當(dāng)然不似!!!接下來,閑著沒事我們模仿sort(),實現(xiàn)一個和sort()方法功能一樣的自定義方法玩玩呀。

??這里不多說，直接上代碼。然后看注釋

Array.prototype._sort.f=function(a,b){ //設(shè)置默認按照Unicode位點進行排序
    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{//否則表示找到插入點了，插入t,并退出循環(huán)
                
                    this[j+1]=t;
                    t=undefined;//將t設(shè)為undefined，防止冒泡未發(fā)生替換就進入插入法排序
                    break;
                    
                }
            }                        
        }            
    }
    return this; //返回排序后的新數(shù)組
}

??到這里就完了？？？No!No!No!雖然我們實現(xiàn)了_sort()方法，但是還有一個不完美的地方。說明第三點說了對undefined的處理規(guī)則，我們還沒有對unfined進行任何處理呢。還需要在上面的排序循環(huán)開始之前添加這樣一段。

//這個循環(huán)把所有數(shù)組undefined的元素和數(shù)組最后一個不是undefined的元素替換
//不同瀏覽器對undefined處理方式不同，這里模仿chrome的處理方式
for(;i=i的條件
    */
    while(this[len-1]===undefined&&len>=i){ 
        len--;
    }
    
    /**
    * 如果len等于i
    * 就表示下標(biāo)不小于i的元素都是undefined了
    * 可以不用繼續(xù)遍歷了
    */
    if(len===i) break; 
    
    /**
    * 使用t將最后一個不是undefined的元素保存起來
    * i in this 是判斷這個元素是不存在，還是值是undefined
    * 數(shù)組中一個不存在的元素，也會返回undefined(稀疏數(shù)組)
    * 這兩者還是有區(qū)別的
    * 如果不存在i in this會返回 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元素
    
    //又塞了一個undefinef到后面，所以要排序的元素又少了一個，再減減一下
    len--; 
    
    }

}

??到這里是真結(jié)束了，謝謝大家！如何有什么我說錯了或者沒說明白的地方，歡迎大家留言一起討論，大家一起學(xué)習(xí)，共同進步么。
??
??
??
??