各种排序算法的js实现

冒泡排序

基本思想：
时间复杂度：

function bubbleSort(arr){
     for (var i = 0; i <arr.length; i++) {
          for (var j= 1; j < arr.length-i;j++) {
               if(arr[j-1]>arr[j]){
                    var tmp=arr[j-1];
                    arr[j-1]=arr[j];
                    arr[j]=tmp;
               }
          };
     };
     return arr;
}

快速排序

基本思想：
时间复杂度：

// 快速排序
function quickSort(arr){
     if(arr.length<=1){
          return arr;
     }

     var pivot=arr[0];
     var left=[],
          right=[];
     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));
}

插入排序

基本思想：
时间复杂度：

// 插入排序
function insertSort(arr){
     for (var i = 1; i < arr.length; i++) {
          var j=i;
          var key=arr[j];
          while(--j>-1){
               if(arr[j]>key){
                    arr[j+1]=arr[j];
               }else{
                    break;
               }
          }
          arr[j+1]=key;
     };
     return arr;
}

归并排序

基本思想：
时间复杂度：

function isArray1(arr){
    if(Object.prototype.toString.call(arr) =='[object Array]'){
        return true;
    }else{
        return false;
    }
}
function merge(left,right){
    var result=[];
    if(!isArray1(left)){
        left = [left];
    }
    if(!isArray1(right)){
        right = [right];
    }
    while(left.length > 0&& right.length >0){
        if(left[0]<right[0]){
            result.push(left.shift());
        }else{
            result.push(right.shift());
        }
    }
    return result.concat(left).concat(right);
}

function mergeSort(arr){
    var len=arr.length;
    var lim ,work=[];
    var i,j,k;
    if(len ==1){
        return arr;
    }
    for(i=0;i<len;i++){
        work.push(arr[i]);
    }
    work.push([]);
    for(lim=len;lim>1;){//lim为分组长度
        for(j=0,k=0;k<lim;j++,k=k+2){
            work[j]=merge(work[k],work[k+1]);
        }
        work[j]=[];
        lim=Math.floor((lim+1)/2);
    }
    return work[0];
}