快速排序

思路

分治：

1. 确定分界点x：q[l], q[(l + r) / 2], q[r], 随机点。

2. 调整区间，将区间分成两个部分，使得第一个区间的所有数都小于等于x，第二个区间的所有数都大于等于x。

3. 递归处理左右两端

第二步的处理方法：

• 方法一：暴力处理。开辟两个数组分别存放小于等于x的和大于x的，最后将两个数组合并。

• 方法二：用两个指针 l 和 r 。l从前往后扫描，r从后往前扫描，两者交替移动。若l发现大于x的数，停止，接着r开始扫描，发现小于等于x的元素停止，让l和r的元素交换，接着两者分别移动一次。

模板：

void quick_sort(int q[], int l, int r) {
	 // 递归终止条件
	if (l >= r) return;

	// 初始化指针和基准值
	int i = l - 1, j = r + 1; 
	int x = q[(l + r) >> 1];

	// 循环用于将数组 `q` 划分为两部分：
	while (i < j) {
		// 从左向右找到第一个不小于 `x` 的元素
		do i++; while (q[i] < x);
		// 从右向左找到第一个不大于 `x` 的元素
		do j--; while (q[j] > x);
		// 确保左边部分都小于等于 `x`，右边部分都大于等于 `x`
		if (i < j) swap(q[i], q[j]);
	}
	// 划分完成后，递归地对左半部分 `q[l, j]` 和右半部分 `q[j+1, r]` 进行快速排序
	quick_sort(q, l, j);
	quick_sort(q, j + 1, r);
}

注意事项

• 基准值 x 选择：

  • 代码中使用的是子数组的中间元素作为基准值：int x = q[(l + r) >> 1];。这种选择在一般情况下是有效的，但在某些特殊情况下（例如，数组已经有序或逆序），可能导致性能退化到最坏情况 (O(n^2))。可以考虑使用随机选择基准值或“三数取中”法来改善这种情况。

  • 可以选择基准值为 q[l] 或 q[r]。当选择基准值为 q[l]的时候，最后递归对左右两部分进行快速排序时，只能用 j，即 quick_sort(q, l, j);quick_sort(q, j + 1, r);。当选择基准值为 q[r]的时候只能用 i，即 quick_sort(q, l, i - 1);quick_sort(q, i + 1, r);

    • 如果基准值选择为 q[r]（即数组的最后一个元素），并且在递归调用时仍然使用 quick_sort(q, l, j); 和 quick_sort(q, j + 1, r);，可能会导致无限递归：

    • 

总结

• 该算法的核心思想是通过选择一个基准元素（这里是中间元素），将数组分为两部分，使得左边部分的元素都小于等于基准值，右边部分的元素都大于等于基准值。

• 然后对这两部分分别递归地进行排序。

• 这种方法的平均时间复杂度为 ()，但在最坏情况下（例如每次选择的基准值都是当前子数组的最大或最小值），时间复杂度为 ()。

进一步增强

添加模板：

template <typename T>
void quick_sort(std::vector<T>& arr, int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1;
    T pivot = arr[(l + r) >> 1];
    while (i < j) {
        do i++; while (arr[i] < pivot);
        do j--; while (arr[j] > pivot);
        if (i < j) std::swap(arr[i], arr[j]);
    }
    quick_sort(arr, l, j);
    quick_sort(arr, j + 1, r);
}

后续可以添加更多改进：

• 将递归的函数进行包装

• 添加支持自定义类型的大小比较，例如传入比较大小的lambda表达式

• 基准选择：可以改进基准选择策略，例如使用随机选择或“三数取中”法来提高效率，尤其是在处理某些特定分布的输入时

• 泛化容器类型：可以进一步泛化以支持其他容器类型（如数组、std::deque等），需要对迭代器进行适当的处理

• 优化小数组排序：对于非常小的数组，直接使用插入排序可能更高效，可以在递归深度达到某个阈值时切换到插入排序

• 并行化：在多核处理器上，可以考虑并行化快速排序的两个递归调用，以提高性能。可以使用C++17的并行算法支持（如std::execution::par）进行并行化

归并排序

模板：

int tmp[N]; // 辅助数组，用于存储合并后的结果

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);

	// 初始化 `k` 为0，用于 `tmp` 数组的索引
	// 使用两个指针 `i` 和 `j` 分别指向左半部分和右半部分的起始位置
	int k = 0, i = l, j = mid + 1;
	
	// 比较 `q[i]` 和 `q[j]`，将较小的元素放入 `tmp` 数组中，并移动相应指针
	while (i <= mid && j <= r) {
		if (q[i] <= q[j]) {
			tmp[k++] = q[i++];
		} else {
			tmp[k++] = q[j++];
		}
	}
	// 处理剩余元素
	// 如果左半部分还有剩余元素，将其全部拷贝到 `tmp` 中。
	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];
	}
}

总结

• 归并排序的时间复杂度为 O(n log n)，空间复杂度为 O(n)。

• 该算法是稳定的，即相等元素的相对顺序在排序后不变。

• 代码中的递归调用和合并步骤是归并排序的核心部分。