1. 冒泡排序

冒泡排序的思想就是不斷進行相鄰交換，較小的數(shù)字如同氣泡般慢慢浮到上面。
優(yōu)化：如果在排第i個元素時，沒有交換任何元素，則排序已完成，無需繼續(xù)遍歷

function mSort(array){
    var flag=true;   //是否還要繼續(xù)排序，排序優(yōu)化
    for(var i=0;i<array.length-1 && flag;i++){
        flag=false;
        for(var j=array.length-2;j>=i;j--){
            if(array[j]>array[j+1]){
                var temp=array[j];
                array[j]=array[j+1];
                array[j+1]=temp;
                flag=true;
            }
        }
    }
}

最好情況：O(n)
最壞情況：O(n^2)
平均情況：O(n^2)

2. 選擇排序

選擇排序的思想是每次遍歷找到最小的元素，然后和相應位置的元素交換位置。

function sSort(array){
    for(var i=0;i<array.length-1;i++){
        //查找最小的元素
        var min=i;
        for(var j=i+1;j<array.length;j++){
            if(array[j]<array[min]){
                min=j;
            }
        }

        //交換位置
        var temp=array[i];
        array[i]=array[min];
        array[min]=temp;
    }
}

最好情況：O(n^2)
最壞情況：O(n^2)
平均情況：O(n^2)
略優(yōu)于冒泡排序。

3.插入排序

插入排序的主要思想是將一個記錄插入到已經安排好的有序表中，需要一個輔助空間來存放這個記錄，以方便前面的元素進行右移。

function iSort(array){
    for(var i=1;i<array.length;i++){
        var temp=array[i];
        //將前面大于其的元素右移
        for(var j=i-1;array[j]>temp && j>=0;j--){
            array[j+1]=array[j];
        }
        //將記錄插入對應位置
        array[j+1]=temp;
    }
}

最好情況：O(n)
最壞情況：O(n^2)
平均情況：O(n^2)
插入排序比冒泡和簡單選擇排序的性能要好。

4.快速排序

快速排序的主要思想是，通過一趟排序將待排序的記錄分割成獨立的兩部分，其中一部分的關鍵字都比另一部分的關鍵字小，則可以對這兩部分繼續(xù)進行排序，以達到整個序列有序的狀態(tài)。
最主要的就是要實現(xiàn)一個partition函數(shù)，可以選取一個樞軸，并將其放在一個合適的位置，使其左側值都比它小，右側值都比它大。

    //快速排序
    function qSort(array,low,high){
        if(low<high){
            var pivot=partition(array,low,high);

            //遞歸排序低子表和高子表
            qSort(array,low,pivot-1);
            qSort(array,pivot+1,high);
        }
    }

    //選取一個關鍵字，放置到合適的位置，左側值都比其小，右側值都比其大
    function partition(array,low,high){
        //設置樞值為第一個元素
        var pivotkey=array[low];

        //交替向中間掃描，直到兩個指針指向同一個位置，即為樞值的位置
        while(low<high){
            while(high>low && array[high]>=pivotkey){
                high--;
            }
            swap(array,low,high);

            while(low<high && array[low]<=pivotkey){
                low++;
            }
            swap(array,low,high);
        }
        return low;
    }

    //交換數(shù)組中a和b的位置
    function swap(array,a,b){
        var temp=array[a];
        array[a]=array[b];
        array[b]=temp;
    }

    var array=[5,4,3,2,1];
    qSort(array,0,array.length-1);
    console.log(array);

快速排序的時間性能取決于其快速排序遞歸的深度，一般partition每次劃分都比較均勻時，其遞歸樹的深度為log2n+1，而每次partition劃分時，需要對數(shù)組的部分做掃描，每一層的時間復雜度為n，所以其時間復雜度為O（nlogn）。
由于關鍵詞的比較和交換時跳躍進行的，因此，快速排序是一種不穩(wěn)定的排序方法。

5.歸并排序

基本思想為分治策略，先將數(shù)組進行劃分，然后再進行合并，關鍵點是實現(xiàn)兩個數(shù)組的合并

//合并兩個數(shù)組
function merge(left,right){
    var res=[];
    while(left.length>0 && right.length>0){
        if(left[0]<=right[0]){
            res.push(left.shift());
        } else {
            res.push(right.shift());
        }
    }
    return res.concat(left).concat(right);
}

//歸并排序
function sort(arr){
    //直到數(shù)組的長度為1，則終止遞歸
    if(arr.length===1){
        return arr;
    }

    var mid=Math.floor(arr.length/2);
    var left=arr.slice(0,mid);
    var right=arr.slice(mid);
    return merge(sort(left),sort(right));
}