【二叉树】

遍历

排序

主要掌握归并排序和快速排序

快速排序

快速排序框架：

void quickSort(vector<int>& nums, int lo, int hi) {
    if (lo > hi) return ;
    // 快排处理：
    // 对 nums[lo..hi] 进⾏切分
    // 使得 nums[lo..p-1] <= nums[p] < nums[p+1..hi]

    int p = partition(nums, lo, hi);
    quickSort(nums, lo, p-1);
    quickSort(nums, p+1, hi);
}

可以发现快排的框架还是在前序遍历的基础进行的部分改动，其构造过程就是一个构造二叉搜索树的过程，这个构造过程可能会出现构造出来的二叉搜索树是极不平衡的情况，为避免这种情况我们引入一些随机性，在排序前对整个数组执行shuffle打乱排序或是在patition函数中随机选择数组元素作为分界点。完整的快速排序代码如下：

class QuickSort {
public:
    void sortArray(vector<int>& nums) {
        shuffle(nums);
        sort(nums, 0, nums.size() -1);
    }

    void sort(vecotr<int>& nums, int lo, int hi) {
        if (lo >= hi) return ;
        int p = partition(nums, lo, hi);
        sort(nums, lo, p-1);
        sort(nums, p+1, hi);
    }

    int partition(vector<int>& nums, int lo, int hi) {
        int pivot = nums[lo];   //选择第一个元素作为判定元素
        // 选择i<= pivot <j
        int 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
            // 此时 [lo, i) <= pivot && (j, hi] > pivot
            if (i >= j) break;
            swap(nums, i, j);
        }
        // 将 pivot 放到合适的位置，即 pivot 左边元素较小，右边元素较大
        swap(nums, lo, j);
        return j;
        
    }
    void swap(vector<int>& nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    void shuffle(vector<int>& nums) {
        int hi = nums.size() - 1;
        for (int i=0; i < nums.size() - 1; i++) {
            int randint = rand()% hi;
            swap(nums, i, randint);
        }
    }

}

归并排序

TODO