快排与三路快排 #

export let quickSort = (arr, left, right) => {
  var len = arr.length,
        partitionIndex,
        left = typeof left != 'number' ? 0 : left,
        right = typeof right != 'number' ? len - 1 : right;

    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
    return arr;
}

const partition = (arr, left, right) => {
  let pivot = left, index = pivot + 1, key = index
  for (let i = index; i <= right; i++) {
    if (arr[i] < arr[pivot]) {
      swap(arr, i, key)
      key++
    }
  }
  swap(arr, pivot, key - 1)
  return key - 1
}
const swap = (arr, i, j) => {
  var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

let quickSort1 = (arr, left, right) => {
  left = typeof left != 'number' ? 0 : left
  right = typeof right != 'number' ? arr.length - 1 : right
  if (left >= right) return arr
  let index = left + 1, key = index
  while(index <= right) {
    if (arr[index] < arr[left]) {
      swap(arr, index, key)
      key++
    }
    index++
  }
  swap(arr, left, key - 1)
  quickSort1(arr, left, key - 2)
  quickSort1(arr, key, right)
  return arr
}

let quickSort2 = (arr, left, right) => {
  left = typeof left === 'number' ? left :0
  right = typeof right === 'number' ? right : arr.length - 1
  let lt = left, index = lt + 1,rt = right + 1
  if (right < left) return arr


  while(index < rt) {
    if (arr[index] < arr[left]) {
      swap(arr, lt+1, index)
      lt++
      index++
    } else if(arr[index] > arr[left]) {
      swap(arr, rt-1, index)
      rt--
    } else {
      index++
    }
  }
  swap(arr, lt, left)
  quickSort2(arr, left, lt -1)
  quickSort2(arr, rt, right)
  return arr
}
let swap = (arr, i, j) => {
  [arr[i], arr[j]] = [arr[j], arr[i]]
}