数据结构与算法 - 归并排序
2022/3/1 12:22:09
本文主要是介绍数据结构与算法 - 归并排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
归并排序
归并字面上的意思是合并,归并算法的核心思想是分治法,就是将一个数组一刀切两半,递归切,直到切成单个元素,然后重新组装合并,单个元素合并成小数组,两个小数组合并成大数组,直到最终合并完成,排序完毕。
我们以[ 8,2,5,9,7 ]
这组数字来举例
首先,一刀切两半:
再切:
再切:
粒度切到最小的时候,就开始归并
数据量设定的比较少,是为了方便图解,数据量为单数,是为了让你看到细节,下面我画了一张更直观的图可能你会更喜欢:
代码实现
void sort(vector<int> &arr) { vector<int> tmp(arr.size()); sort(arr, tmp, 0, arr.size()-1); } void sort(vector<int> &arr, vector<int> &tmp, int start, int end) { if(end <= start) return; } void sort(vector<int> &arr, vector<int> &tmp, int start, int end) { if(end <= start) return; int mid = start + (end - start) / 2; sort(arr, tmp, start, mid); sort(arr, tmp, mid+1, end); merge(arr, tmp, start, mid, end); } void merge(vector<int>& arr, vector<int>& tmp, int start, int mid, int end) { for(int i = start; i <= end; i++) { tmp[s] = arr[s]; } int left = start; int right = mid +1; for(int j = start; j <= end; j++) { if(left > mid) { //如果左边的首位下标大于中部下标,证明左边的数据已经排完了。 arr[j] = tmp[right++]; } else if(right > end) { //如果右边的首位下标大于了数组长度,证明右边的数据已经排完了。 arr[j] = tmp[left++]; } else if(tmp[right] < tmp[left]) { //将右边的首位排入,然后右边的下标指针+1。 arr[j] = tmp[right++]; } else { //将左边的首位排入,然后左边的下标指针+1。 arr[j] = tmp[left++]; } } }
我们可以发现 merge 方法中只有一个 for 循环,直接就可以得出每次合并的时间复杂度为 \(O(n)\) ,而分解数组每次对半切割,属于对数时间 \(O(\log n)\) ,合起来等于 \(O(\log_2{n})\) ,也就是说,总的时间复杂度为 \(O(n\log n)\) 。
这篇关于数据结构与算法 - 归并排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)