快排
分治
核心是将一个复杂的问题分解为若干个规模较小的子问题，这些子问题相互独立且与原问题是同类的。将子问题逐个解决之后，再将子问题的解合并，从而得到原问题的解。
主要三个步骤：
-
分解：选择一个基准元素（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;
}
