SOURCE

/**
 * 先从后往前找
 * 再从前往后找
 * 72、6、57、88、60、42、83、73、48、85
 * voit = 0
 * left = 1
 * right = length
 * 从后向前找小的放在voit位置
 * 从前向后找大的放在小的位置
 */
function quickSort (arr, l, r) {
  var l = l || 0;
  var r = r || arr.length - 1;
  var i = AdjustArray(arr, l, r);
  if (l < i - 1) {
    quickSort(arr, l, i - 1);
  }
  if (r > i + 1) {
    quickSort(arr, i + 1, r);
  }

}
function AdjustArray (arr, l, r) {
  var i = l;
  var j = r;
  // i是一个坑
  var x = arr[l];
  while (i < j) {
    while (i < j && arr[j] >= x) {
      j--;
    }
    // 找到比x小的放入i
    // j成为一个坑
    // j等于x
    if (i < j) {
      arr[i] = arr[j];
      i++;
    }
    while (i < j && arr[i] < x) {
      i++;
    }
    // 找到比x大的数字放入j
    // 相当于arr[i]>arr[j]
    // i成为新的坑
    if (i < j) {
      arr[j] = arr[i];
      j--;
    }
  }
  arr[i] = x;
  return i;
}
var arr = [10, 4, 7, 3, 5, 6, 2, 8, 1];
quickSort(arr);
console.log(arr);