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

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

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

定義

sort() 方法在適當的位置對數組的元素進行排序，并返回數組。 sort 排序不一定是穩定的。

語法

arr.sort()

arr.sort(compareFunction)

說明

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

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

3.如果數組包含undefined元素（元素值為undefined或元素末定義）  
以上90%引用自MDN

實例

//例1.字母排序
var a = new Array("banna","watermelon","orange","apple");
s.sort(); 
console.log(a) //輸出 ["apple", "banna", "orange", "watermelon"]
//沒什么好說的，比較函數缺省，按照字母順序升序排序 a.5?-1:1; //根據說明2-c特性，實現隨機排序
});
console.log(a) //每次運行的輸出都不同

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

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

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]
*/

??不知道同學們有沒有看出什么端倪。反正我一開始是什么都沒有發現，那就分析分析咯。
??第一次1和8比較，1<8，不需要調整位置。
??第二次8和3比較，8>3，需要調整位置。但是這里沒有交換位置，僅僅是8覆蓋了3位置。這里就可以推斷出不是單純的使用了冒泡算法。
??第三是1和3比較，1<3，3替換了8的位置。什么鬼，幾個意思？？？看到這里我也是表示不懂呀。那就繼續往下看咯。
??第四是8和5比較，8>5，又僅僅是覆蓋，沒有交換位置。還是不懂，繼續往下！
??第五是3和5比較，3<5，5替換了8的位置，不懂，繼續往下！
??第六是8和-1比較，8>-1， 還僅僅是覆蓋，繼續往下！
??第七、八、九次，-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]
*/

??沒跑了，這就是插入法。再捋捋，第一次冒泡完之后，前兩位肯是有序的。第二次比較，如果發生位變化，a先向后移動一位，b沒有直接前移，而是通過插入法找到正確的位置插入，此時前三位有序。如果沒有發生位置變化，說明此時前三位已經有序，繼續拿有序的最后一位和之后的一位比較。如此循環，直至整個數組有序。

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

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

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

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

Array.prototype._sort.f=function(a,b){ //設置默認按照Unicode位點進行排序
    a+="",b+="";
    return a0){ //大于零則需要交接位置
            t=this[i+1],this[i+1]=this[i];
        }
        
        /**
        * 如果t值是unfeined，
        * 則當前的這次騎比較沒有發生位置變化
        * 也就不需要使用插入法了
        */
        if(t){
            //使用插入法找到正確的插入位置，上面排序算法還有優化插入法排序的方法
            for(var j=i-1;j>=0;j--){
            
                if(f(this[j],t)>0){//如果當前元素大于t,則當前元素后移一位
                
                    this[j+1]=this[j];
                    
                }else{//否則表示找到插入點了，插入t,并退出循環
                
                    this[j+1]=t;
                    t=undefined;//將t設為undefined，防止冒泡未發生替換就進入插入法排序
                    break;
                    
                }
            }                        
        }            
    }
    return this; //返回排序后的新數組
}

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

//這個循環把所有數組undefined的元素和數組最后一個不是undefined的元素替換
//不同瀏覽器對undefined處理方式不同，這里模仿chrome的處理方式
for(;i=i的條件
    */
    while(this[len-1]===undefined&&len>=i){ 
        len--;
    }
    
    /**
    * 如果len等于i
    * 就表示下標不小于i的元素都是undefined了
    * 可以不用繼續遍歷了
    */
    if(len===i) break; 
    
    /**
    * 使用t將最后一個不是undefined的元素保存起來
    * i in this 是判斷這個元素是不存在，還是值是undefined
    * 數組中一個不存在的元素，也會返回undefined(稀疏數組)
    * 這兩者還是有區別的
    * 如果不存在i in this會返回 false
    */
    t=this[len-1];
    if(i in this)
        this[len-1]=undefined; //元素值為undefined，直接將要替換元素值設為undefined
    else
        delete this[len-1]; //元素不存在，通過刪除將要替換的元素設置為不存在，
    
    this[i]=t; //替換undefined元素
    
    //又塞了一個undefinef到后面，所以要排序的元素又少了一個，再減減一下
    len--; 
    
    }

}

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