写一个快排 about front-end-interview HOT 2 OPEN

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  var pivotIndex = Math.floor(arr.length / 2),
    pivot = arr.splice(pivotIndex, 1)[0];
  var left = [],
    right = [];
  for (var i = 0; i < arr.length; i++) {
    if (pivot > arr[i]) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return quickSort(left).concat([pivot], quickSort(right));
}

function quickSort1(array, left, right) {
  // 最开始不输入left和right参数
  var left = typeof left == "number" ? left : 0,
    right = typeof right == "number" ? right : array.length - 1;

  if (left < right) { //只要左指针不小于右指针就继续partition
    var index = partition(array, left, right);
    quickSort1(array, left, index - 1);
    quickSort1(array, index + 1, right);
  }
  return array;
}

var partition = function (array, left, right) {
  var pivot = array[Math.floor((right + left) / 2)];
  while (left <= right) {
    while (array[left] < pivot) {
      left++;
    }
    while (array[right] > pivot) {
      right--;
    }
    if (left <= right) {
      [array[left], array[right]] = [array[right], array[left]];
      left++;
      right--;
    }
  }
  return left;
};