快速排序与归并排序模板

快排

分治

核心是将一个复杂的问题分解为若干个规模较小的子问题，这些子问题相互独立且与原问题是同类的。将子问题逐个解决之后，再将子问题的解合并，从而得到原问题的解。

主要三个步骤：

分解：选择一个基准元素（pivot），然后将数组分割成两个子数组。其中一个子数组的所有元素都小于基准元素，另一个子数组的所有元素都大于基准元素。
递归：对两个子数组（小于基准元素的子数组和大于基准元素的子数组）进行递归快排，直到每个子数组的大小减少为 1 或 0，此时它们自然有序。
合并：当递归结束时，子数组都是有序的，所以整个数组就变为有序。

分区过程：

选择基准元素：第一个、最后一个、随机一个、中间的。
双指针扫描：使用两个指针，一个称为“左指针”或“较小元素指针”，另一个称为“右指针”或“较大元素指针”。左指针从数组的起始位置向右移动，寻找第一个大于等于基准元素的元素。右指针从数组的结束位置向左移动，寻找第一个小于等于基准元素的元素。当这两个指针相遇时，分区完成。此时，将左指针和右指针指向的元素进行交换。
确定基准元素的位置：分区结束后，将基准元素放在中间位置，使得左边的所有元素都小于等于基准元素，右边的所有元素都大于等于基准元素。

分区过程

数组 [6, 2, 5, 4, 3, 1, 2, 4]，选择中间元素 5 作为基准元素。

左指针从索引 0 开始，找到第一个大于等于 5 的元素，即 6。
右指针从索引 7 开始，找到第一个小于等于 5 的元素，即 4。
交换这两个元素，数组变为 [4, 2, 5, 4, 3, 1, 2, 6]。
继续移动指针，左指针找到下一个大于等于 5 的元素，右指针找到小的元素，直到左指针超过右指针，交换结束。

分区结果：

[4, 2, 3, 4, 1, 2, 5, 6]

现在，基准元素 5 处于正确的位置，左边的元素都小于等于它，右边的元素都大于等于它。

快排板子

#include <algorithm>
#include <iostream>
using namespace std;

void quickSort(int nums[], int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1;
    int m = nums[(l + r) >> 1];
    while (i < j) {
        while (nums[++i] < m);
        while (nums[--j] > m);
        if (i < j) {
            swap(nums[i], nums[j]);
        }
    }
    quickSort(nums, l, j);
    quickSort(nums, j + 1, r);
}

int main() {
    int nums[] = {6, 2, 5, 4, 3, 1, 2, 4};
    int n = sizeof(nums) / sizeof(nums[0]);
    quickSort(nums, 0, n - 1);
    for (int i = 0; i < n; ++i) {
        cout << nums[i] << " ";
    }
    cout << endl;
    return 0;
}

归并

核心思想也是分治。不断地将数组分割成更小的部分，直到每个部分只有一个元素（此时它们自然有序），然后再将这些有序的小部分合并成一个有序的较大的部分，最终得到整个数组的有序排列。
快排是先分界再递归，归并是先递归完再分界。

归并板子

#include <iostream>
using namespace std;
int tmp[10000]; 

void merge_sort(int q[], int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1; 
    merge_sort(q, l, mid); 
    merge_sort(q, mid + 1, r); 

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];

    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];

    for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}

int main() {
    int nums[] = {5, 3, 8, 6, 4, 1, 9, 7, 2};
    int n = sizeof(nums) / sizeof(nums[0]);
    merge_sort(nums, 0, n - 1);
    for (int i = 0; i < n; ++i) {
        cout << nums[i] << " ";
    }
    cout << endl;

    return 0;
}