算法二叉树

二叉树前置思想

快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后序遍历。(听说高手都是这么想的)
所以先打点基础吧。

快排算法思路

代码框架

1
2
3
4
5
6
7
8
9
10
11
const sort = function(nums, lo, hi) {
    if (lo >= hi) {
        return;
    }
    // 对 nums[lo..hi] 进行切分
    // 使得 nums[lo..p-1] <= nums[p] < nums[p+1..hi]
    let p = partition(nums, lo, hi);
    // 去左右子数组进行切分
    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
};

对比二叉树前序遍历

1
2
3
4
5
6
7
8
9
10
11
// 二叉树遍历框架
const traverse = function(root) {
    if (root === null) {
        return;
    }
    // ***** 前序位置 *****
    console.log(root.val);
    // *******************
    traverse(root.left);
    traverse(root.right);
};

一句话总结快速排序：快速排序是先将一个元素排好序，然后再将剩下的元素排好序。

快速排序的核心无疑是 partition 函数， partition 函数的作用是在 nums[lo..hi] 中寻找一个切分点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]

一个元素左边的元素都比它小，右边的元素都比它大，所以 partition 函数干的事情，其实就是把 nums[p] 这个元素排好序了。

从二叉树的视角，我们可以把子数组 nums[lo..hi] 理解成二叉树节点上的值，sort 函数理解成二叉树的遍历函数。

partition 函数每次都将数组切分成左小右大两部分，恰好和二叉搜索树左小右大的特性吻合。

欸☝️🤓，那快速排序的过程可不就是是一个构造二叉搜索树的过程。

但是二叉搜索树不平衡的极端情况，需要引入随机性，比如洗牌算法。当然这种东西就不是现在的我能碰瓷的了，随便记一下就好了。

快速排序代码实现

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
39
40
41
42
43
44
45
46
47
48
49
const quickSort = function(nums) {
   
    // 排序整个数组（原地修改）
    sort(nums, 0, nums.length - 1);
};

const sort = function(nums, lo, hi) {
    if (lo >= hi) {
        return;
    }
    // 对 nums[lo..hi] 进行切分
    // 使得 nums[lo..p-1] <= nums[p] < nums[p+1..hi]
    let p = partition(nums, lo, hi);
    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
};

// 对 nums[lo..hi] 进行切分
const partition = function(nums, lo, hi) {
   let pivot = nums[lo];
    // 关于区间的边界控制需格外小心，稍有不慎就会出错
    // 这里把 i, j 定义为开区间，同时定义：
    // [lo, i) <= pivot；(j, hi] > pivot
    // [lo, i) <= pivot; (j, hi] > pivot
    // 之后都要正确维护这个边界区间的定义
   let i = lo + 1, j = hi;
    // 当 i > j 时结束循环，以保证区间 [lo, hi] 都被覆盖
    while (i <= j) {
        while (i < hi && nums[i] <= pivot) {
            i++;
            // 此 while 结束时恰好 nums[i] > pivot
        }
        while (j > lo && nums[j] > pivot) {
            j--;
            // 此 while 结束时恰好 nums[j] <= pivot
        }

        if (i >= j) {
            break;
        }
        // 此时 [lo, i) <= pivot && (j, hi] > pivot
        // 交换 nums[j] 和 nums[i]
        [nums[i], nums[j]] = [nums[j], nums[i]];
        // 此时 [lo, i] <= pivot && [j, hi] > pivot
    }
    // 最后将 pivot 放到合适的位置，即 pivot 左边元素较小，右边元素较大
    [nums[lo], nums[j]] = [nums[j], nums[lo]];
    return j;
};