Ayingotts's notes

Appearance

原地快排 ​

以 number[] 为例，快速排序的优化：

  1. 选择一个标志位
  2. 使用双指针，左指针找到最接近但小于标志位的元素，右侧指针找到最接近但大于标志位的元素
  3. 左指针位置小于右侧指针位置时，左右指针位置元素交换
  4. 标志位和左指针位置元素交换 ( 左指针位置元素必小于标志位元素 )

时间复杂度：O(n * lgn)

空间复杂度：O(1)

ts
function sort<T = number>(arr: T[], start: number, end: number) {
  // 取标志位
  const init = start
  const flag = arr[init]

  // 左指针从标志位右侧一位开始
  start += 1

  while (start <= end) {
    while (arr[end] > flag) {
      end -= 1
    }

    while (arr[start] < flag) {
      start += 1
    }

    // 满足条件时，交换左右指针位置元素
    if (start < end) {
      ;[arr[start], arr[end]] = [arr[end], arr[start]]
      start += 1
      end -= 1
    }
  }

  // 交换标志位与左指针位置元素
  ;[arr[init], arr[start - 1]] = [arr[start - 1], arr[init]]
  return start
}

function quickSortInPlace<T = number>(arr: T[], start: number, end: number): T[] {
  if (start < end) {
    const index = sort(arr, start, end)
    quickSortInPlace(arr, start, index - 1)
    quickSortInPlace(arr, index, end)
  }

  return arr
}
function sort<T = number>(arr: T[], start: number, end: number) {
  // 取标志位
  const init = start
  const flag = arr[init]

  // 左指针从标志位右侧一位开始
  start += 1

  while (start <= end) {
    while (arr[end] > flag) {
      end -= 1
    }

    while (arr[start] < flag) {
      start += 1
    }

    // 满足条件时，交换左右指针位置元素
    if (start < end) {
      ;[arr[start], arr[end]] = [arr[end], arr[start]]
      start += 1
      end -= 1
    }
  }

  // 交换标志位与左指针位置元素
  ;[arr[init], arr[start - 1]] = [arr[start - 1], arr[init]]
  return start
}

function quickSortInPlace<T = number>(arr: T[], start: number, end: number): T[] {
  if (start < end) {
    const index = sort(arr, start, end)
    quickSortInPlace(arr, start, index - 1)
    quickSortInPlace(arr, index, end)
  }

  return arr
}