快速排序。quick sort

quickSort.js

function partition(arr, left, right) {
  var poivtIndex = Math.floor((left + right) / 2); // 中间位置作为分割点
  var leftIndex = left;
  var rightIndex = right;
  while(leftIndex <= rightIndex) {
    while(arr[leftIndex] < arr[poivtIndex]) { // 分割点左边较小的跳过
      leftIndex += 1;
    }
    while(arr[rightIndex] > arr[poivtIndex]) { // 分割点右边较大的跳过
      rightIndex -= 1;
    }
    if(leftIndex <= rightIndex) { // 遇到了分割点左边较大且右边较小的情况
      // 交换，以使得分割点右边都较大，左边都较小
      var temp = arr[leftIndex];
      arr[leftIndex] = arr[rightIndex];
      arr[rightIndex] = temp;
      
      leftIndex += 1;
      rightIndex -= 1;
    }
  }
  return leftIndex; // 得到新的分割点
}

function quickSort(arr, left, right) {
  var len = arr.length;
  if(len < 2) return arr;
  left = typeof left === 'number' ? left : 0;
  right = typeof right === 'number' ? right : len - 1;
  var piovtIndex = partition(arr, left, right);
  if(left < piovtIndex - 1) {
    quickSort(arr, left, piovtIndex - 1);
  }
  if(right > piovtIndex) {
    quickSort(arr, piovtIndex, right);
  }
  return arr;
}