day7

归并排序
概述：
归并排序是一种基于分治法的排序算法。它将数组分成两个子数组，递归地对这两个子数组进行排序，然后将两个已排序的子数组合并成一个有序的数组。
步骤：
将待排序的数组分成两半。
递归地对这两个子数组进行排序。
合并两个已排序的子数组以形成一个有序的数组。
时间复杂度：
最好情况：O(n log n)
平均情况：O(n log n)
最坏情况：O(n log n)
空间复杂度： O(n)（需要额外的空间来存储合并过程中的数组）
特点：
稳定排序算法（不会改变相同元素的相对顺序）。
适合处理大规模数据。
需要额外的空间来存储中间结果。
C++ 确实是一个非常强大的编程语言，在性能和控制方面具有很大的优势。它被广泛用于系统编程、游戏开发、实时系统等对性能有高要求的领域。下面是归并排序和快速排序的 C++ 实现代码示例：
// 合并两个已排序的子数组
void merge(std::vector& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
std::vector L(n1);
std::vector R(n2);
// 将数据复制到临时数组 L[] 和 R[]
for (int i = 0; i < n1; ++i)
L[i] = arr[left + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[mid + 1 + j];
// 合并临时数组到原数组
int i = 0;
int j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
// 复制剩余的元素
while (i < n1) {
arr[k++] = L[i++];
}
while (j < n2) {
arr[k++] = R[j++];
}
}
// 递归排序
void mergeSort(std::vector& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}

快速排序
概述：
快速排序是一种高效的排序算法，同样基于分治法。它通过选择一个“基准”元素，将数组划分为比基准元素小的部分和比基准元素大的部分，然后递归地对这两个部分进行排序。
步骤：
选择一个基准元素（通常是数组中的一个元素）。
将数组分成两个部分：小于基准元素的部分和大于基准元素的部分。
递归地对两个部分进行排序。
合并已排序的部分（不需要额外的合并步骤，因为原地排序）。
时间复杂度：
最好情况：O(n log n)（当基准元素能均匀地划分数组时）
平均情况：O(n log n)
最坏情况：O(n²)（当基准元素选择不佳时，例如已排序数组）
空间复杂度： O(log n)（递归栈空间）
特点：
非稳定排序算法（可能会改变相同元素的相对顺序）。
大多数情况下非常高效，适合处理大规模数据。
实现时需要选择合适的基准元素以避免最坏情况。
例：
// 分区函数，选择基准元素并将小于基准的元素放在左边，大于基准的元素放在右边
int partition(std::vector& arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1);

for (int j = low; j <= high - 1; ++j) {
if (arr[j] < pivot) {
++i;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return (i + 1);
}
// 递归快速排序函数
void quickSort(std::vector& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}