var bubbleSort = function (arr) {
 var flag = true;
 var len = arr.length;
 for (var i = 0; i < len - 1; i++) {
  flag = true;
  for (var j = 0; j < len - 1 - i; j++) {
   if (arr[j] > arr[j + 1]) {
    var temp = arr[j+1];
    arr[j+1] = arr[j];
    arr[j] = temp;
    flag = false;
   }
  }
  if (flag) {
   break;
  }
 }
}; 

 var selectSort = function (arr) {
 var min;
 for (var i = 0; i < arr.length-1; i++) {
  min = i;
  for (var j = i + 1; j < arr.length; j++) {
   if (arr[min] > arr[j]) {
    min = j;
   }
  }
  if (i != min) {
   swap(arr, i, min);
  }
 }
};
function swap(arr, index1, index2) {
 var temp = arr[index1];
 arr[index1] = arr[index2];
 arr[index2] = temp;
}; 

 var insertSort = function (arr) {
 var len = arr.length, key;
 for (var i = 1; i < len; i++) {
  var j = i;
  key = arr[j];
  while (--j > -1) {
   if (arr[j] > key) {
    arr[j + 1] = arr[j];
   } else {
    break;
   }
  }
  arr[j + 1] = key;
 }
}; 

 var shellSort = function (arr) {
 var gaps = [5, 3, 1];
 for (var g = 0; g < gaps.length; ++g) {
  for (var i = gaps[g]; i < arr.length; ++i) {
   var temp = arr[i];
   for (var j = i; j >= gaps[g] && arr[j - gaps[g]] > temp; j -= gaps[g]) {
    arr[j] = arr[j - gaps[g]];
   }
   arr[j] = temp;
  }
 }
}; 

 function mergeSort(arr) {
 if (arr.length < 2) {
  return;
 }
 var step = 1;
 var left, right;
 while (step < arr.length) {
  left = 0;
  right = step;
  while (right + step <= arr.length) {
   mergeArrays(arr, left, left + step, right, right + step);
   left = right + step;
   right = left + step;
  }
  if (right < arr.length) {
   mergeArrays(arr, left, left + step, right, arr.length);
  }
  step *= 2;
 }
}
function mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) {
 var rightArr = new Array(stopRight - startRight + 1);
 var leftArr = new Array(stopLeft - startLeft + 1);
 k = startRight;
 for (var i = 0; i < (rightArr.length - 1); ++i) {
  rightArr[i] = arr[k];
  ++k;
 }
 k = startLeft;
 for (var i = 0; i < (leftArr.length - 1); ++i) {
  leftArr[i] = arr[k];
  ++k;
 }
 rightArr[rightArr.length - 1] = Infinity; // 哨兵值
 leftArr[leftArr.length - 1] = Infinity; // 哨兵值
 var m = 0;
 var n = 0;
 for (var k = startLeft; k < stopRight; ++k) {
  if (leftArr[m] <= rightArr[n]) {
   arr[k] = leftArr[m];
   m++;
  }
  else {
   arr[k] = rightArr[n];
   n++;
  }
 }
} 

 var quickSort = function(arr, left, right) {
 var i, j, t, pivot;
 if (left >= right) {
  return;
 }
 pivot = arr[left];
 i = left;
 j = right;
 while (i != j) {
  while (arr[j] >= pivot && i < j) {
   j--;
  }
  while (arr[i] <= pivot && i < j) {
   i++;
  }
  if (i < j) {
   t = arr[i];
   arr[i] = arr[j];
   arr[j] = t;
  }
 }
 arr[left] = arr[j];
 arr[j] = pivot;
 quickSort(arr, left, i - 1);
 quickSort(arr, i + 1, right);
}