基本排序算法-快速排序

发表于 分类于

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
 * @Description: quickSort
 * @Author: libk
 * @Github: https://github.com/libk
 */
function partition (arr, left, right) {
  let random = Math.floor(Math.random() * (right - left + 1)) + left
  let povit = arr[random]

  ;[arr[random], arr[left]] = [arr[left], arr[random]]
  while (left < right) {
    while (left < right && arr[right] >= povit) {
      right--
    }
    if (left < right) {
      arr[left++] = arr[right]
    }
    while (left < right && arr[left] < povit) {
      left++
    }
    if (left < right) {
      arr[right--] = arr[left]
    }
  }
  arr[left] = povit
  return left
}
function quickSort (arr, left = 0, right = arr.length - 1) {
  if (!arr || arr.length < 2) {
    return
  }
  if (right > left) {
    let index = partition(arr, left, right)
    quickSort(arr, left, index - 1)
    quickSort(arr, index + 1, right)
  }
}