快速排序

function exchange(arr, i, j) {
  const temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

function split(arr, start, end) {
  const target = arr[start]
  let mid = start
  for (let i = start + 1; i <= end; i++) {
    if (arr[i] < target) {
      mid++
      exchange(arr, i, mid)
    }
  }
  exchange(arr, mid, start)
  return mid
}

function quickSort(arr, start, end) {
  if (start >= end) {
    return
  }
  // 必须保证 mid 左侧比 mid 值小，右侧比 mid 值大
  // 才能确保就算 split 没有进行位置交换也能缩小区间
  const mid = split(arr, start, end)
  quickSort(arr, start, mid - 1)
  quickSort(arr, mid + 1, end)
  return arr
}

function sort(arr) {
  quickSort(arr, 0, arr.length - 1)
  return arr
}

测试代码

console.log(sort([5, 8, 6, 3, 9, 2, 1, 7]))
console.log(sort([3, 4, 2, 1, 5, 6, 7, 8]))
console.log(sort([2, 3, 4, 5, 6, 7, 8, 1]))
console.log(sort([4, 4, 6, 5, 3, 2, 8, 1]))

双边循环

function split(arr, start, end) {
  const target = arr[start]
  let left = start
  let right = end
  while (left < right) {
    // 必须先移动右指针，使得最终停留的位置一定属于左区间，才能最终返回 left
    while (right > left && arr[right] > target) {
      right--
    }
    // 相等也要右移，因为一开始一定是相等的
    while (left < right && arr[left] <= target) {
      left++
    }
    exchange(arr, left, right)
  }
  exchange(arr, left, start)
  return left
}

非递归实现

function quickSort(arr, a, b) {
  const stack = [[a, b]]
  while (stack.length) {
    const [start, end] = stack.shift()
    if (start >= end) {
      continue
    }
    // 必须保证 mid 左侧比 mid 值小，右侧比 mid 值大
    // 才能确保就算 split 没有进行位置交换也能缩小区间
    const mid = split(arr, start, end)
    stack.push([start, mid - 1])
    stack.push([mid + 1, end])
  }
}