# 快速排序

公司: 这个频率比较高。。。对于前端来说,算基础考点

leetcode:912:排序树组题链

给你一个整数数组 nums,请你将该数组升序排列。

# 相关属性

  • 时间复杂度
    • 平均时间复杂度:O(N*logN)
    • 最坏情况下:O(N²)
      • 排序一个已经有序的数组,退化成冒泡排序,每一次都只能确定基准数的位置

# 交换法

原理参考-【坐在马桶上看算法】快速排序

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
    const swap = (arr, i, j) => {
        [arr[i], arr[j]] = [arr[j], arr[i]]
    }

    const _quickSort = (arr, left, right) => {
        if (left >= right) {
            return
        }
        let o = left
        let i = left, j = right
        while (left !== right) {
            // 先从右往左动
            while (arr[right] >= arr[o] && left < right) {
                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(nums, 0, nums.length - 1)
    return nums
};
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

# 填坑法

原理参考-漫画:什么是快速排序?(完整版)

function quickSort(data) {
    const _quickSort = (arr, left, right) => {
        if (left >= right) {
            return
        }
        let o = arr[left] // 选择的基数
        let oIndex = left // 当前的坑位置
        const i = left
        const j = right
        while (left < right) {
            while (left < right) {
                if (arr[right] < o) {
                    arr[oIndex] = arr[right] // 填坑
                    oIndex = right // 新坑
                    left++
                    break
                }
                right--
            }
            while (left < right) {
                if (arr[left] > o) {
                    arr[oIndex] = arr[left] // 填坑
                    oIndex = left // 新坑
                    right--
                    break
                }
                left++
            }
        }

        arr[oIndex] = o // 基数入坑
        // 开始下一轮
        _quickSort(arr, i, oIndex - 1)
        _quickSort(arr, oIndex + 1, j)
    }
    _quickSort(data, 0, data.length - 1)
    return data
}
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
38