# 快速排序

  • 平均时间复杂度:O(N*logN)
  • 最坏情况下:O(N²)
function quickSort(array) {
    const _quickSort = (arr, left, right) => {
        if (left > right) {
            return
        }
        let i = left, j = right
        let o = left
        while (left !== right) {
            while (arr[right] >= arr[o] && right > left) {
                right--
            }

            while (arr[left] <= arr[o] && left < right) {
                left++
            }

            if (left < right) {
                swap(arr, left, right)
            }
        }
        swap(arr, o, left)
        _quickSort(arr, i, left - 1)
        _quickSort(arr, left + 1, j)
    }
    _quickSort(array, 0, array.length - 1)
}
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