**实验报告：分治法实现归并排序算法**
一、实验背景
归并排序是一种基于分治策略的高效排序算法，其主要思想是将大问题分解为小问题，然后逐个解决，最后再将小问题的解组合成大问题的解。本实验旨在通过实际编程实现归并排序算法，理解分治法的原理，并验证其时间复杂性。
二、分治法介绍
分治法是一种重要的算法设计策略，适用于解决可分解为多个相同或相似子问题的问题。其一般步骤包括以下三个阶段：
1. **Divide（分解）**：将原问题分解为若干个规模较小的子问题。
2. **Conquer（解决）**：递归地解决这些子问题，如果子问题规模足够小，可以直接求解。
3. **Combine（合并）**：将子问题的解合并为原问题的解。
三、归并排序算法详解
归并排序的核心在于它的分治过程。算法伪代码如下：
```markdown
MERGESORT(low, high)
if low < high
mid = (low + high) / 2
MERGESORT(low, mid) // 对左半部分进行排序
MERGESORT(mid + 1, high) // 对右半部分进行排序
MERGE(low, mid, high) // 归并已排序的两部分
MERGE(low, mid, high)
// 使用辅助数组B进行归并
for h = low, i = low, j = mid + 1; h <= mid and j <= high
if A[h] <= A[j]
B[i] = A[h], h++
else
B[i] = A[j], j++
i++
// 处理剩余元素
if h > mid
for k = j to high
B[i] = A[k], i++
else
for k = h to mid
B[i] = A[k], i++
// 将已归并的集合复制回A
```
归并排序的时间复杂度为O(n log n)，空间复杂度为O(n)。
四、快速排序算法简介
快速排序是另一种高效的排序算法，同样采用分治策略。其基本思想是选取一个“划分元素”，将数组分为两部分，使得一部分所有元素都小于划分元素，另一部分所有元素都大于划分元素，然后对这两部分分别进行快速排序。算法伪代码如下：
```markdown
QuickSort(p, q)
if p < q
j = Partition(p, q + 1)
QuickSort(p, j - 1)
QuickSort(j + 1, q)
Partition(m, p)
// 将A[m]作为划分元素，移动元素使得A[i] < A[m] < A[j]
v = A[m]
i = m, j = p
while i < j
i++
while A[i] < v
i++
j--
while A[j] >= v
j--
if i < j
INTERCHANGE(A[i], A[j])
A[m] = A[j]
A[j] = v
return j
```
快速排序平均时间复杂度为O(n log n)，最坏情况为O(n^2)，但这种情况较为罕见。
五、实验内容及步骤
1. 编写C++代码实现归并排序，同时记录比较次数。
2. 输入10组相同数据，执行排序并输出比较次数，确保排序正确。
3. 比较理论复杂性计算的比较次数与实际运行结果。
4. 制作表格对比理论与实验数据。
5. 分析实验结果，讨论归并排序的效率和适用场景。
六、代码示例
```cpp
#include<iostream>
using namespace std;
void merge(int arr[], int l, int m, int r) {
// ... 实现归并操作
}
void mergeSort(int arr[], int l, int r) {
if(l < r) {
int m = l+(r-l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
// 其他辅助函数...
int main() {
// ... 输入数据，调用mergeSort，输出结果和比较次数
return 0;
}
```
通过以上实验，我们可以深入理解分治法在解决实际问题中的应用，特别是归并排序算法的工作原理。此外，还可以对比归并排序与其他排序算法（如快速排序）的优劣，进一步提升对算法设计和分析的理解。
