javascript數組（1） ——sort的工作原理及其他數組排序方法

一說到數組排序，最直觀的想法就是用sort啊！

請問不用使用sort方法還可以使用什麼方法進行數組排序？

比如 ：  快速排序法、合併排序法、冒泡排序法、選擇排序法、插入排序法、布爾排序法、交互排序、選擇排序、二分法排序.....

等等一下，在我們瞭解這些排序方法之前，為了更好的理解，先讓我們探索一下sort的工作原理

//  sort()方法：按照字元編碼的順序進行排序
     var arr = [11,15,20,1000,25,2,40]
     arr.sort();          // [1000, 11, 15, 2, 20, 25, 40]

//  sort()的兩種使用方法：
//  1.不帶參數，比較字元串字母的排序
     var alpha =["I","L","O","V","E","W","E","B"]
     alpha.sort();      //["B", "E", "E", "I", "L", "O", "V", "W"]
 
//  2.帶參數，比較數字或大小
     var arr1 = [11,15,20,1000,25,2,40]
     function order (a,b){
           if(a>b){return 100;}   
           if(a<b){return -100;}  
           if(a==b){return 0;}   
     }
//  此方法還可以簡化
    function order (a,b){
           return a-b
     }
//  a,b  分別取值進行比較，當a>b時為正數，當a<b時為負數，當a=b時為零。
     arr.sort(order);    //[2, 11, 15, 20, 25, 40, 1000]

 舉了上面一系列的例子，相信大家對sort排序也有了初步的認知。那麼，sort排序的工作原理是什麼呢？

工作原理：先比較第一個和第二個排序，再比較第三個，以此類推

下麵我們來說說其他排序方法，並且比較程式的運行速度

快速排序法

快速排序使用分治法來把一個串（list）分為兩個子串（sub-lists）。具體演算法描述如下：

（1）在數據集之中，選擇一個元素作為"基準"（pivot）。

（2）所有小於"基準"的元素，都移到"基準"的前面；所有大於"基準"的元素，都移到"基準"的後面。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作；

（3）遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。

function quicksort(arr){
    if(arr.length == 0){return arr;}
    var pivot =arr[0];
    var left =new Array();
    var right = new Array();
    for (var i=1;i<arr.length;i++){
        if(arr[i]<pivot){
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quicksort(left).concat(pivot,quicksort(right));

}
console.time('快速排序Tiem');
console.log(quicksort(arr));
console.timeEnd('快速排序Tiem');

合併排序法

如果列表的長度為0或1，那麼它已被排序。除此以外：

（1）將未排序的列表劃分為大約一半大小的兩個子列表。

（2）通過重新應用合併排序來遞歸地排序每個子列表。

（3）將兩個子列表合併成一個排序列表。

function mergeSort(arr){
    if (arr.length < 2)
        return arr;
    var middle = parseInt(arr.length / 2);
    var left   = arr.slice(0, middle);
    var right  = arr.slice(middle, arr.length);
    return merge(mergeSort(left), mergeSort(right));
}
 
function merge(left, right){
    var result = [];
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    } 
    while (left.length)
        result.push(left.shift());
 
    while (right.length)
        result.push(right.shift());
 
    return result;
}
console.time('合併排序Tiem');
console.log(mergeSort(arr));
console.timeEnd('合併排序Tiem');

冒泡排序法

具體演算法描述如下：

（1）比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；

（2）對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對，這樣在最後的元素應該會是最大的數；

（3）針對所有的元素重覆以上的步驟，除了最後一個；

（4）重覆步驟 （1）（3）（1）（3），直到排序完成。

function bubbleSort(arr) {
    var i = 0,
    len = arr.length,
    j, d;
    for (; i < len; i++) {
        for (j = 0; j < len; j++) {
            if (arr[i] < arr[j]) {
                d = arr[j];
                arr[j] = arr[i];
                arr[i] = d;
            }
        }
    }
    return arr;
}
console.time('冒泡排序Tiem');
console.log(bubbleSort(arr));
console.timeEnd('冒泡排序Tiem');

 排序方法還有很多，在這裡就不一一詳解了，想瞭解更多可以查閱javascript排序演算法彙總（寫的很不錯的哦~！）

最後為大家推薦一個日本程式員norahiko，寫的排序動畫站，希望能夠對數組排序的學習有所幫助๑乛◡乛๑