首页 / 算法 / 常用排序算法之——归并排序
常用排序算法之——归并排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了常用排序算法之——归并排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1571字，纯文字阅读大概需要3分钟。
内容图文
归并排序的原理：
如果数组的元素个数大于1，则：
将数组平均分为两部分；
左边的数组归并排序；递归
右边的数组归并排序；递归
将两个各自有序的数组合并，需要一个额外的辅助数组，暂时保存合并结果；返回
否则，数组元素个数为1时，已经有序；直接返回。
稳定排序。时间复杂度在最坏、最好、平均情况下都为O(N lgN)，空间复杂度为O(N)。
代码：
1 #include <iostream>
2usingnamespace std;
3 4 template<typename T>
5void mergeSortedArray(T src[], int first, int mid, int last, T tmp[])
6{
7int i = first, j = mid + 1;
8int idx = 0;
910while(i <= mid && j <= last)
11 {
12 tmp[idx++] = src[i] < src[j] ? src[i++] : src[j++];
13 }
1415while(i <= mid)
16 {
17 tmp[idx++] = src[i++];
18 }
19while(j <= last)
20 {
21 tmp[idx++] = src[j++];
22 }
2324for(i = 0; i < idx; ++i)
25 {
26 src[first + i] = tmp[i];
27 }
28}
2930 template<typename T>
31void mergeSort(T src[], int first, int last, T tmp[])
32{
33if(first >= last)
34return;
3536int mid = first + ((last - first) >> 1); //找到中间元素下标，将数组分为两部分
3738 mergeSort(src, first, mid, tmp); //排序左边子数组
39 mergeSort(src, mid + 1, last, tmp);
4041 mergeSortedArray(src, first, mid, last, tmp); //合并，tmp为辅助数组，用于记录临时合并的结果
42}
4344int main()
45{
46constint n = 5;
4748int ia[n] = {1, 3, 6, 2, 4};
49int itmp[n];
50 mergeSort(ia, 0, n - 1, itmp); //sort51for(int i = 0; i < n; ++i)
52 cout << ia[i] << ‘‘;
53 cout << endl;
5455double da[n] = {1.2, 3.4, 6.7, 2.3, 4.5};
56double dtmp[n];
57 mergeSort(da, 0, n - 1, dtmp); //sort58for(int i = 0; i < n; ++i)
59 cout << da[i] << ‘‘;
60 cout << endl;
61 return 0;
62 }
原文：http://www.cnblogs.com/qieerbushejinshikelou/p/3905817.html
内容总结
以上是互联网集市为您收集整理的常用排序算法之——归并排序全部内容，希望文章能够帮你解决常用排序算法之——归并排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。