// 冒泡排序 每次將最小元素推至最前,效率較低霞赫，生產(chǎn)環(huán)境中很少使用显熏。
  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;
  }

  // 改進(jìn)冒泡排序：
  // 如果在某次的排序中沒(méi)有出現(xiàn)交換的情況，
  // 那么說(shuō)明在無(wú)序的元素現(xiàn)在已經(jīng)是有序了，就可以直接返回了。
  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;
  }

  //選擇排序
  // 在無(wú)序區(qū)中選出最小的元素，然后將它和無(wú)序區(qū)的第一個(gè)元素交換位置。
  // 原理跟冒泡排序一樣区转，算是冒泡的衍生版本
  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;
  }

  // 插入排序 從下標(biāo)1開(kāi)始每增1項(xiàng)排序一次，越往后遍歷次數(shù)越多,比冒泡和選擇排序有效率
  function sort4(array) {
    var len = array.length,
        i, j, tmp, result;

    // 設(shè)置數(shù)組副本
    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;
  }
 
  // 二分插入排序
  // 先在有序區(qū)通過(guò)二分查找的方法找到移動(dòng)元素的起始位置版扩，
  // 然后通過(guò)這個(gè)起始位置將后面所有的元素后移
  function sort5(array) {
    var len = array.length,
        i, j, tmp, low, high, mid, result;
    // 賦予數(shù)組副本
    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;
  }

  // 合并排序
  // 前面三種排序算法只有教學(xué)價(jià)值废离，因?yàn)樾实停苌賹?shí)際使用礁芦。合并排序（Merge sort）則是一種被廣泛使用的排序方法蜻韭。
  // 它的基本思想是，將兩個(gè)已經(jīng)排序的數(shù)組合并宴偿，要比從頭開(kāi)始排序所有元素來(lái)得快湘捎。因此，可以將數(shù)組拆開(kāi)窄刘，分成n個(gè)只有一個(gè)元素的數(shù)組窥妇，然后不斷地兩兩合并，直到全部排序完成娩践。
  function sort6(array){
    var result = array.slice(0);

    // 遞歸調(diào)用合并函數(shù)
    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）是公認(rèn)最快的排序算法之一活翩，有著廣泛的應(yīng)用烹骨。
  //（1）在數(shù)據(jù)集之中，選擇一個(gè)元素作為"基準(zhǔn)"（pivot）材泄。
  //（2）所有小于"基準(zhǔn)"的元素沮焕，都移到"基準(zhǔn)"的左邊；所有大于"基準(zhǔn)"的元素拉宗，都移到"基準(zhǔn)"的右邊峦树。
  //（3）對(duì)"基準(zhǔn)"左邊和右邊的兩個(gè)子集，不斷重復(fù)第一步和第二步旦事，直到所有子集只剩下一個(gè)元素為止魁巩。
  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;
  }