SOURCE

var arr = [3,6,2,4,7,1,9,10,11, 50, 37,25,23,18, 34, 56, 44,29, 5, 90, 42];
/** 插入排序(从小到达) **/
function insertSort(arr) {
  for(var i = 2, len = arr.length; i < len; i++) {
    if(temp < arr[i-1]) {
      arr[0] = arr[i]; // arr[0]作为哨兵
      for(var j = i-1; arr[0] < arr[j]; j--) {
        arr[j+1] = arr[j];
      }
      arr[j+1] = arr[0];
    }
  }
}
// insertSort(arr)

/** 快速排序 **/
function fastSort(arr, start, end) {
  if(start < end){return}
  var pivot = arr[end];
  var i = start -1, j = end;
  while(i < j) {
    while(arr[++i] < pivot);
    while(arr[--j] > pivot);
    if(i < j) {
      // 交换a,b两个值同时不引入变量
      // a = a - b; b = a + b; a = b - a;
      arr[i] = arr[i] - arr[j];
      arr[j] = arr[i] + arr[j];
      arr[i] = arr[j] - arr[i];
    }
  }
  arr[end] = arr[i];
  arr[i] = pivot;
  fastSort(arr, start, i -1);
  fastSort(arr, i + 1, end);
}
// fastSort(arr, 0, arr.length -1);

/** 归并排序 **/
var helpArr=[];
function Merge(arr, low, mid, high) {
  for(var k = 0; k <= high; k++) {
    helpArr[k] = arr[k];
  }
  for(var i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
    if(helpArr[i] < helpArr[j]) {
      arr[k] = helpArr[i++];
    } else {
      arr[k] = helpArr[j++];
    }
  }
  while(i <= mid) {
    arr[k++] = helpArr[i++];
  }
  while(j <= high) {
    arr[k++] = helpArr[j++];
  }
}

function MergeSort(arr, low, high) {
  if(low < high) {
    var mid = Math.floor((low + high) / 2);
    MergeSort(arr, low, mid);
    MergeSort(arr, mid+1, high);
    Merge(arr, low, mid, high);
  }
}
// MergeSort(arr, 0, arr.length -1);

/** 希尔排序，gaps是间隔序列 **/
function shellSort(arr, gaps) {
  var arr_len = arr.length;
  var gaps_len = gaps.length;
  for(var g = 0; g < gaps_len; g++) { // 间隔序列长度，比如6个间隔序列
    for(var i = gaps[g]; i < arr_len; i++) {
      // 这里每个进行直接插入排序
      var temp = arr[i];
      for(var j = i; j >= 0 && arr[j-gaps[g]] > temp; j-=gaps[g]) {
        arr[j] = arr[j-gaps[g]]
      }
      arr[j] = temp
    }
  }
}

/** 堆排序(大顶堆) **/
function heapMaxSort(arr) {
  
}

// 根据某个节点，调整堆
function adjustDown(arr, nodeIdx, len) {
  arr[0] = arr[nodeIdx];
  for(var i = 2*nodeIdx; i <= len; i*=2) {
    if(i < len && arr[i] < arr[i+1]) {
      i++
    }
    if(arr[0] >= arr[i]){
      break;
    } else {
      arr[nodeIdx] = arr[i];
      nodeIdx = i;
    }
  }
}

/** 冒泡排序 **/
function bubbleSort(arr) {
  var len = arr.length;
  var temp;
  for(var i = len - 1; i > 0; i--) {
    for(var j = 0; j < i; j++) {
      if(arr[j] > arr[j+1]) {
        temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
}

/** 选择排序 **/
function selectionSort(arr) {
  var len = arr.length;
  var min_idx;
  for(var i = 0; i < len; i++) {
    min_idx = i;
    for(var j = i + 1; j < len; j++) {
      if(arr[j] < arr[min_idx]) {
        min_idx = j;
      }
    }
    var temp = arr[i];
    arr[i] = arr[min_idx];
    arr[min_idx] = temp;
  }
}


// console.log(arr);