快排

2023-06-16 10:31:21

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

  // 选择基准元素
  const pivotIndex = Math.floor(arr.length / 2)
  const pivot = arr[pivotIndex]

  // 分成两个子数组
  const left = []
  const right = []
  for (let i = 0; i < arr.length; i++) {
    if (i !== pivotIndex) {
      if (arr[i] < pivot) {
        left.push(arr[i])
      } else {
        right.push(arr[i])
      }
    }
  }

  // 递归排序子数组
  return [...quickSort(left), pivot, ...quickSort(right)]
}