这篇文章主要讲解了“c++如何实现二路归并排序”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“c++如何实现二路归并排序”吧!
二路归并排序
基本思想
二路归并排序就是将两个有序子表归并成一个有序表。首先我们得有一个算法用于归并:两个有序表放在同一数组的相邻位置上,arr[left]到arr[center-1]为第一个有序表,arr[center]到arr[right]是第二个有序表。每次从两端中取出一个进行比较,小的先放在一个temp数组,最后将比较剩下的直接放到temp中去,最后将temp又复制回arr。这是“治”。
所谓“分”,就是递归地将前半部分和后半部分的数据各自归并排序即可。
算法分析
每一趟归并的时间复杂度为O(n),共需要进行⌈log2n⌉趟。对应的算法的时间复杂度为O(nlog2n)。归并排序的空间复杂度O(n)。另外,归并排序中归并的算法并不会将相同关键字的元素改变相对次序,所以归并排序是稳定的。
二路归并排序的前提是两个序列本身有序。
void Merger(int *arr, int len, int width) { int *temp =(int *)malloc(sizeof(int) * (len)); //首先对两路下标分别进行初始化 int l1 = 0; int h2 = l1 + width - 1; int l2 = h2 + 1; int h3 = l2 + width - 1 < len - 1 ? l2 + width - 1 : len - 1; int temppos = 0; //判断所在下标位置的值 while (l1 < len && l2 < len) { while (l1 <= h2 && l2 <= h3) { if (arr[l1] < arr[l2]) { temp[temppos++] = arr[l1++]; } else { temp[temppos++] = arr[l2++]; } } //l1有剩余 while (l1 <= h2) { temp[temppos++] = arr[l1++]; } //l2有剩余 while (l2 <= h3) { temp[temppos++] = arr[l2++]; } //l1 l2向后移动 l1 = h3 + 1; h2 = (l1 + width - 1) < (len - 1) ? (l1 + width - 1) : (len - 1); l2 = h2 + 1; h3 = (l2 + width - 1) < (len - 1) ? (l2 + width - 1) : (len - 1); } //奇数归并块 剩下的一个单都块操作 while (l1PS:二路合并排序算法
#includeusing namespace std; class SortableList { public: SortableList(int mSize) { maxSize = mSize; l= new int[maxSize]; n = 0; } ~SortableList() { delete[]l; } void Merge(int, int, int); void MergeSort(int,int); void Input(); void Output(); private: int* l; int maxSize; int n; }; void SortableList::Input() { cout << "请输入要排序的数:"; for (int i = 0; i <= maxSize - 1; i++) cin >> l[i]; } void SortableList::Output() { cout << "排序后的数是:"; for (int i = 0; i <= maxSize - 1; i++) cout << l[i]<<' '; } void SortableList::MergeSort(int left,int right) { if (left < right)//如果序列长度大于1则划分 { int mid = (left + right) / 2; MergeSort(left, mid);//对左序列进行排序 MergeSort(mid + 1, right);//对右序列进行排序 Merge(left, mid, right);//合并 } } void SortableList::Merge(int left, int mid, int right) { int* temp= new int[right - left + 1]; int i = left, j = mid + 1, k = 0; while ((i <= mid) && (j <= right))//判断序列是否为空 if (l[i] <= l[j]) temp[k++] = l[i++]; else temp[k++] = l[j++]; while (i <= mid) temp[k++] = l[i++];//右序列空了左序列依次写入 while (j <= right) temp[k++] = l[j++];//左序列空了右序列依次写入 for (i = 0, k = left; k <= right;) l[k++] = temp[i++];//临时在数组temp中的排列好的数据放入数组l } int main() { int m; cout << "请输入要排序的数的数目:"; cin >> m; SortableList a1(m); a1.Input(); a1.MergeSort(0, m-1); a1.Output(); } 感谢各位的阅读,以上就是“c++如何实现二路归并排序”的内容了,经过本文的学习后,相信大家对c++如何实现二路归并排序这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是创新互联建站,小编将为大家推送更多相关知识点的文章,欢迎关注!
另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
本文标题:c++如何实现二路归并排序-创新互联
文章URL:http://cdkjz.cn/article/hdged.html