常见排序算法

  // 冒泡排序 每次将最小元素推至最前,效率较低，生产环境中很少使用。
  function sort1(array) {
    var len = array.length,
        i,j,tmp;
    var result = array.slice(0);
    for(i=0;i<len;i++){
      for(j=len-1;j>i;j--){
        if(result[j]<result[j-1]){
          tmp = result[j];
          result[j] = result[j-1];
          result[j-1] = tmp;
        }
      }
    }
    return result;
  }

  // 改进冒泡排序：
  // 如果在某次的排序中没有出现交换的情况，
  // 那么说明在无序的元素现在已经是有序了，就可以直接返回了。
  function sort2(array) {
    var len = array.length,
    i, j, tmp, exchange, result;

    result = array.slice(0);
    for (i = 0; i < len; i++) {
      exchange = 0;
      for (j = len - 1; j > i; j--) {
        if (result[j] < result[j - 1]) {
          tmp = result[j];
          result[j] = result[j - 1];
          result[j - 1] = tmp;
          exchange = 1;
        }
      }
      if (!exchange) return result;
    }
    return result;
  }

  //选择排序
  // 在无序区中选出最小的元素，然后将它和无序区的第一个元素交换位置。
  // 原理跟冒泡排序一样，算是冒泡的衍生版本
  function sort3(array){
    var result = array.slice(0),
        len = array.length,
        i,j,k,tmp;
    for(i=0;i<len;i++){
      k = i;
      for(j=i+1;j<len;j++){
        if(result[j]<result[k]) k = j
      }
      if(k!==i){
        tmp = result[k];
        result[k] = result[i];
        result[i] = tmp;
      }
    }
    return result;
  }

  // 插入排序 从下标1开始每增1项排序一次，越往后遍历次数越多,比冒泡和选择排序有效率
  function sort4(array) {
    var len = array.length,
        i, j, tmp, result;

    // 设置数组副本
    result = array.slice(0);
    for(i=1; i < len; i++){
      tmp = result[i];
      j = i - 1;
      while(j>=0 && tmp < result[j]){
        result[j+1] = result[j];
        j--;
      }
      result[j+1] = tmp;
    }
    return result;
  }
 
  // 二分插入排序
  // 先在有序区通过二分查找的方法找到移动元素的起始位置，
  // 然后通过这个起始位置将后面所有的元素后移
  function sort5(array) {
    var len = array.length,
        i, j, tmp, low, high, mid, result;
    // 赋予数组副本
    result = array.slice(0);
    for(i = 1; i < len; i++){
      tmp = result[i];
      low = 0;
      high = i - 1;
      while(low <= high){
        mid = parseInt((low + high)/2, 10);
        if(tmp < result[mid]) high = mid - 1;
        else low = mid + 1;
      }
      for(j = i - 1; j >= high+1; j--){
        result[j+1] = result[j];            
      }
      result[j+1] = tmp;
    }
    return result;
  }

  // 合并排序
  // 前面三种排序算法只有教学价值，因为效率低，很少实际使用。合并排序（Merge sort）则是一种被广泛使用的排序方法。
  // 它的基本思想是，将两个已经排序的数组合并，要比从头开始排序所有元素来得快。因此，可以将数组拆开，分成n个只有一个元素的数组，然后不断地两两合并，直到全部排序完成。
  function sort6(array){
    var result = array.slice(0);

    // 递归调用合并函数
    function sort(arr){
      var mid = Math.floor(arr.length/2),
          left = arr.slice(0,mid),
          right = arr.slice(mid,arr.length);

      if(arr.length === 1){
        return arr;
      }

      return merge(sort(left),sort(right));
    }
    
    function merge(left,right){
      var result = [];
      while(left.length || right.length){
        if(left.length && right.length){
          if(left[0]<right[0]){
            result.push(left.shift())
          }else{
            result.push(right.shift())
          }
        }else if(left.length){
          result.push(left.shift())
        }else{
          result.push(right.shift())
        }
      }
      return result;
    }

    return sort(array);
  }

  // 快速排序（quick sort）是公认最快的排序算法之一，有着广泛的应用。
  //（1）在数据集之中，选择一个元素作为"基准"（pivot）。
  //（2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
  //（3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
  function sort7(array){
    var tmp_array = array.slice(0),result;
    var quickSort = function(arr){
      var left = [],right = [];
      if(arr.length<=1) {return arr;}
      var pivotIndex = Math.floor(arr.length/2);
      var pivot = arr.splice(pivotIndex,1)[0];
      for(var i =0;i<arr.length;i++){
        if(arr[i]<pivot){
          left.push(arr[i])
        }else{
          right.push(arr[i])
        }
      }
      return quickSort(left).concat(pivot,quickSort(right))
      
    };
    result = quickSort(tmp_array);
    return result;
  }