风动之石的博客

快速排序

示意图

快速排序示意图

实现

function quickSort(arr, left, right) {
    left = left !== undefined ? left : 0
    right = right !== undefined ? right : arr.length - 1

    if (left < right) {
        const partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex - 1)
        quickSort(arr, partitionIndex + 1, right)
    }
    return arr
}

function partition(arr, left, right) {
    const pivot = left;
    let index = pivot + 1;
    for (let i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index)
            index++
        }
    }
    swap(arr, pivot, index - 1)
    return index - 1
}

function swap(arr, i, j) {
    const temp = arr[j]
    arr[j] = arr[i]
    arr[i] = temp
}
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

结合示意图和代码，来了解如何分区的：

  • pivot是基准（黄色），分区时要与这个数做比较，将所有数字分为比基于小的部分和比基准大的部分
  • index是下一个要被替换的位置，index位置左边的数都比pivot小
  • 在分区过程中，绿色表示比基准pivot小的，紫色表示比基准pivot大的（第一个紫色表示index），红色表示当前i，
  • 每一次循环后，要把pivot与index - 1的数互换，返回新的pivot位置，即index - 1

如果示意图过快无法了解分区过程，可以将gif图下载到本地，一帧一帧查看。

复杂度分析

时间复杂度

  • 最好情况：每次递归都平分数组，移动需要递归O(logn)次，每次递归需要遍历n次，时间复杂度为O(nlogn)
  • 最差情况：每次递归都把数组分为1和n-1，一共需要递归n次，每次递归需要遍历n次，时间复杂度为O(n^2)
  • 平均时间复杂度：O(nlogn)

空间复杂度

  • 最好情况：O(logn)
  • 最差情况：O(n)
  • 平均空间复杂度：O(logn)

注意，空间复杂度不是O(1)，因为每次递归都在不同的函数栈里，每次递归时需要O(1)空间，且不同函数栈里的O(1)空间不能复用。

Reference