几种排序（javascript）

先写快排吧,时间复杂度为O(nlogn)，时间复杂度由渐进符号O符号表示，f(n) = O(g(n))，表示f(n)的复杂度最多与g(n)一个数量级，即小于等于。

思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

Array.prototype.quickSort=function(){    //快排  
    var arr=this;
    if (arr.length <= 1) { return arr; }
    var index= Math.floor(arr.length/2);
    //   var pivot = arr.splice(index,1)[0];
    var pivot = arr[index];
    var left=[];
    var right=[];
    for(var i=0;i<arr.length;i++){
        if(i==index){continue;}
        if(arr[i]>pivot){right.push(arr[i])}
        else{left.push(arr[i])}
    }
    return left.quickSort().concat([pivot], right.quickSort());
}

归并排序：（可以用于外排序，把几组已经排好序的集合归并到一组）

function　merge(left, right){  
    var　result=[];
    while(left.length>0 && right.length>0){
        if(left[0]<right[0]){
        /*shift()方法用于把数组的第一个元素从其中删除，并返回第一个元素的值。*/
            result.push(left.shift());
        }else{
            result.push(right.shift());
        }
    }
    return　result.concat(left).concat(right);
}
function　mergeSort(items){  //items数组  
    if(items.length == 1){
        return　items;
    }
    var　middle = Math.floor(items.length/2),
    left = items.slice(0, middle),
    right = items.slice(middle);
    return　merge(mergeSort(left),mergeSort(right));
}

堆排序:

Array.prototype.swap=function(i,j){   //交换元素  
    var tmp=this[i];
    this[i]=this[j];
    this[j]=tmp;
};

Array.prototype.heapSort=function(f){            //堆排序  
    var fn=f;;
    if(f==null){
        fn=function(a,b){return a-b;}
    }

    var that=this;
    buildHeap();
    for(var i=that.length-1;i>0;i--){
        that.swap(0,i);
        heapAdjust(0,i);
    }
    return that;
    function heapAdjust(i,j){
        var M=i;
        var left=i*2+1;
        var right=i*2+2;
        if(left<j&&fn(that[M],that[left])<0){
            M=left;
        }
        if(right<j&&fn(that[M],that[right])<0){
            M=right;
        }
        if(M!=i){
            that.swap(i,M);
            heapAdjust(M,j);
        }
    }
    function buildHeap(){
        for(var i=Math.floor(that.length/2)-1;i>=0;i--){
            heapAdjust(i,that.length);
        }
    }
}