#快速排序

function sortArray(nums: number[]): number[] {
  if (nums.length <= 1) {
    return nums
  }

  // 最后一个数为基准
  const pivot = nums[nums.length - 1]
  const less = []
  const greater = []

  // 分为比基准大和比基准小两个数组
  for (let i = 0; i < nums.length - 1; i++) {
    if (nums[i] < pivot) {
      less.push(nums[i])
    } else {
      greater.push(nums[i])
    }
  }

  // 递归
  return [...sortArray(less), pivot, ...sortArray(greater)]
}

function sortArray(nums: number[]): number[] {
  if (nums.length <= 1) {
    return nums
  }

  quickSort(nums, 0, nums.length - 1)

  return nums
}

function quickSort(nums: number[], left: number, right: number) {
  if (left < right) {
    // 分区并返回基准下标
    const pivotIndex = partition(nums, left, right)
    console.log(nums)
    // 递归排序左边
    quickSort(nums, left, pivotIndex - 1)
    // 递归排序右边
    quickSort(nums, pivotIndex + 1, right)
  }

  return nums
}

function partition(nums: number[], left: number, right: number) {
  // 假设基准值在最右
  const pivot = nums[right]
  // 左边更小数组的尾下标(初始基准下标)
  let i = left

  // 注意最右边基准值单独处理
  for (let j = left; j < right; j++) {
    // 如果数小于等于基准值，交换到左边数组
    if (nums[j] < pivot) {
      ;[nums[i], nums[j]] = [nums[j], nums[i]]
      i++
    }
  }

  // 交换最右边基准值到左边数组尾部(基准下标位置)
  ;[nums[i], nums[right]] = [nums[right], nums[i]]

  return i
}