基础知识

优先介绍时间复杂度为 $O(log(N))$ 的算法，其余 $O(n^2)$ 的直接复制粘贴在底部。

1. 快速排序

1. 选择基准元素：从待排序的数组中选择一个基准元素，通常选择最后一个元素 (也可以选择第一个元素、随机元素、三数取中等)。
2. 分区过程：将数组中的元素重新排列，使得小于基准元素的值位于基准元素的左侧，大于基准元素的值位于右侧。
3. 递归排序：对左右两个子数组分别进行递归排序，重复上述两个步骤。
4. 合并结果：最后，将左子数组、基准元素和右子数组合并起来，得到排序完成的数组。

public class Note2_1_QuickSort {
    // 快速排序方法
    public static void quickSort(int[] q, int l, int r) {
        if (l >= r) return;
        // TODO 1 注意是 l - 1 和 r + 1 让下文从第一个数就开始比较
        int i = l - 1, j = r + 1;
        int x = q[(l + r) >> 1];

        while (i < j) {
            // TODO 2 不要弄反顺序
            do i++; while (q[i] < x);
            do j--; while (q[j] > x);
            if(i < j) swap(q, i, j);
        }

        // TODO 3 以 j 为基准
        quickSort(q, l, j);
        quickSort(q, j + 1, r);

    }

    // 交换数组中的两个元素
    private static void swap(int[] q, int i, int j) {
        int temp = q[i];
        q[i] = q[j];
        q[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {1, -1, 3, 2};
        quickSort(arr,0, arr.length - 1);
        for (int item : arr) {
            System.out.println("item = " + item);
        }
    }
}

24.1.15更：这里会出现两个问题

1. while(q[i]<x);while(q[j]>x);为什么不能改为 while(q[i]<=x);while(q[j]>=x);？

问题在于如果我们的基准x刚好取到最大/最小值，就会发生指针越界。 如数组4 2 1 5 3 , 第一轮迭代时 x = 1, q[i] = 4，q[j] = 1 但如果把等号加上，q[j] = 1 时就不会停下来，一直往左走直到越界。

1. 为什么不能将quick_sort(q, l, j); quick_sort(q, j + 1, r);改成 quick_sort(q, l, i); quick_sort(q, i + 1, r);

因为 l + r >> 1 是向下取整 ， 如果 | l - j | = 1 , 那么 l + j >> 1 = l，那么递归到最后 j = l就是 quick_sort(q , l , l)就结束了， 不会死循环，如果用 i 做边界，x的取值还是q[l + r >> 1], 那最后 | i - l | = 1, quick_sort(q , l , i)执行完了 l 和 i 的值还没变，还是quick_sort(q , l , i)，就死循环了。

换种说法就是，每次快排，数据范围都得改变（缩小）直到 缩到一个数，避免缩小到两个数的时候 ，数据范围不变，一直是那两个数，所以就得选用合适的边界：

1. x = q[l + r >> 1] , quick_sort(q , l , j) , quick_sort(q , j + 1 , r)
2. x = q[l + r + 1>> 1] , quick_sort(q , l , i - 1) , quick_sort(q , i , r)

所以到最后我们只需要记住两件事：