C++实现归并排序（MergeSort）

归并排序

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)，且它是一种稳定的排序算法，适合大规模数据的排序。

文件下载

评论信息

其他资源

免责申明

【只为小站】的资源来自网友分享，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，【只为小站】无法对用户传输的作品、信息、内容的权属或合法性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论【只为小站】经营者是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，zhiweidada#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见版权及免责申明

C++实现归并排序（MergeSort）

文件下载

评论信息

其他资源

免责申明

个人信息

相关资源标签

热门下载

最新下载