C++实现归并排序（MergeSort） 在这里，我们将详细介绍C++实现归并排序（MergeSort）的知识点。归并排序是一种稳定的排序算法，它的思路是将数组不断地分割成两个子序列，直到每个子序列只有一个元素为止，然后将这些子序列从小到大合并为一个序列。 我们来看一下归并排序的思路： 1. 划分：一直调用划分过程，直到子序列为空或只有一个元素为止，共需log2(n)。 2. 归并：将两个子序列从小到大合并为一个序列。 下面是C++实现归并排序的程序代码： ```c #include using namespace std; // 合并两个有序的序列 template void Merge(T arr[], int start, int mid, int end) { int i, j, k, n1, n2; k = 0; n1 = mid - start + 1; n2 = end - mid; T *L = new T[n1], *R = new T[n2]; for (i = 0; i < n1; i++) // 将arr的左部分赋给L L[i] = arr[start + i]; for (j = 0; j < n2; j++) // 将arr的右部分赋给R R[j] = arr[mid + j + 1]; i = 0; j = 0; k = start; while (i < n1 && j < n2) { // 合并 if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { // 左部分没处理完 arr[k] = L[i]; k++; i++; } while (j < n2) { // 右部分没处理完 arr[k] = R[j]; k++; j++; } delete[] L; delete[] R; } // 归并排序 template void MergeSort(T arr[], int start, int end) { int mid; if (start >= end) return; mid = (start + end) / 2; MergeSort(arr, start, mid); MergeSort(arr, mid + 1, end); Merge(arr, start, mid, end); } // 输出数组 template void Print(T arr[], int n) { int i; for (i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; } int main(int argc, const char *argv[]) { int n, i, arr[50]; cout << "请输入要排序的数的个数："; cin >> n; srand((int)time(NULL)); // 设置时间为随机点 for (i = 0; i < n; i++) // 产生n个随机数 arr[i] = rand() % 100; cout << "排序前："; Print(arr, n); MergeSort(arr, 0, n - 1); // 调用归并排序 cout << "排序后："; Print(arr, n); return 0; } ``` 通过上面的代码，我们可以看到，归并排序的实现是通过递归地将数组分割成两个子序列，然后将这些子序列从小到大合并为一个序列。我们可以通过Print函数来输出排序后的结果。 C++实现归并排序是一种高效的排序算法，它的时间复杂度为O(n log n)，且它是一种稳定的排序算法，适合大规模数据的排序。

使用C++书写的归并排序算法，希望对各位有用。也请大牛指教代码中有何不足的地方！

MergeSort合并排序

用C/C++语言编程实现归并分类算法6.3 和快速分类算法6.6。对于快速分类，SPLIT中的划分元素采用三者A(low)，A(high)，A((low+high)/2)中其值居中者。 （2）随机产生20组数据（比如n=5000i，1≤i≤20）。数据均属于范围（0，105）内的整数。对于同一组数据，运行快速分类和归并分类算法，并记录各自的运行时间（以毫秒为单位）。 （3）根据实验数据及其结果来比较快速分类和归并分类算法的平均时间，并得出结论。