[数据结构与算法] 归并排序
2021/11/22 11:39:53
本文主要是介绍[数据结构与算法] 归并排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录
- 归并排序
- 1.概念
- 2.算法原理
- 3.动态演示
- 4.代码
- 5.性能
归并排序
1.概念
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法,归并排序对序列的元素进行逐层折半分组,然后从最小分组开始比较排序,合并成一个大的分组,逐层进行,最终所有的元素都是有序的。
2.算法原理
3.动态演示
4.代码
void _MergeSort(int* a, int left, int right, int* tmp) { //递归终止条件 if (left >= right) { return; } int mid = (left + right) / 2; //[left, mid] mid [mid+1, right] 有序 _MergeSort(a, left, mid, tmp); _MergeSort(a, mid + 1, right, tmp); int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; int i = left; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } //如果[begin1,end1]区间没有结束 while (begin1<=end1) { tmp[i++] = a[begin1++]; } //如果[begin2,end2]区间没有结束 while (begin2 <= end2) { tmp[i++] = a[begin2++]; } //tmp 数组的值拷贝回a for (int j = left; j <= right; ++j) { a[j++] = tmp[j]; } } //归并排序 void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { printf("malloc failed!\n"); exit(-1); } _MergeSort(a, 0, n - 1, tmp); free(tmp); tmp = NULL; }
5.性能
- 时间复杂度:O(N*logN)
- 空间复杂度:O(N)
- 稳定性:稳定
这篇关于[数据结构与算法] 归并排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南