经典排序算法 - 归并排序Merge sort
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了经典排序算法 - 归并排序Merge sort，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1880字，纯文字阅读大概需要3分钟。
内容图文
经典排序算法 - 归并排序Merge sort
原理,把原始数组分成若干子数组,对每一个子数组进行排序,
继续把子数组与子数组合并,合并后仍然有序,直到全部合并完,形成有序的数组
举例
无序数组[6 2 4 1 5 9]
先看一下每个步骤下的状态,完了再看合并细节
第一步 [6 2 4 1 5 9]原始状态
第二步 [2 6] [1 4] [5 9]两两合并排序,排序细节后边介绍
第三步 [1 2 4 6] [5 9]继续两组两组合并
第四步 [1 2 4 5 6 9]合并完毕,排序完毕
输出结果[1 2 4 5 6 9]
合并细节
详细介绍第二步到第三步的过程,其余类似
第二步:[2 6] [1 4] [5 9]
两两合并,其实仅合并[2 6] [1 4],所以[5 9]不管它,
原始状态
第一个数组[2 6]
第二个数组[1 4]
--------------------
第三个数组[...]
第1步,顺序从第一,第二个数组里取出一个数字:2和1
比较大小后将小的放入第三个数组,此时变成下边这样
第一个数组[2 6]
第二个数组[4]
--------------------
第三个数组[1]
第2步,继续刚才的步骤,顺序从第一,第二个数组里取数据,2和4,
同样的比较大小后将小的放入第三个数组,此时状态如下
第一个数组[6]
第二个数组[4]
--------------------
第三个数组[1 2]
第3步,再重复前边的步骤变成,将较小的4放入第三个数组后变成如下状态
第一个数组[6]
第二个数组[...]
--------------------
第三个数组[1 2 4]
第4步,最后将6放入,排序完毕
第一个数组[...]
第二个数组[...]
--------------------
第三个数组[1 2 4 6]
[ 1 2 4 6 ]与[ 5 9 ]的合并过程与上边一样,不再分解
代码仅供参考
static
void merge(int[] unsorted, int first, int mid, int last, int[] sorted)
{
int i = first, j = mid;
int k = 0;
while (i < mid && j < last)
if (unsorted[i] < unsorted[j])
sorted[k++] = unsorted[i++];
else
sorted[k++] = unsorted[j++];
while (i < mid)
sorted[k++] = unsorted[i++];
while (j < last)
sorted[k++] = unsorted[j++];
for (int v = 0; v < k; v++)
unsorted[first + v] = sorted[v];
}
staticvoid merge_sort(int[] unsorted, int first, int last, int[] sorted)
{
if (first + 1 < last)
{
int mid = (first + last) / 2;
Console.WriteLine("{0}-{1}-{2}", first, mid, last);
merge_sort(unsorted, first, mid, sorted);
merge_sort(unsorted, mid, last, sorted);
merge(unsorted, first, mid, last, sorted);
}
}
staticvoid Main(string[] args)
{
int[] x = { 6, 2, 4, 1, 5, 9 };
int[] sorted = newint[x.Length];
merge_sort(x, 0, x.Length, sorted);
for (int i = 0; i < sorted.Length; i++)
{
if (x[i] > 0)
Console.WriteLine(x[i]);
}
Console.ReadLine();
}
原文：http://blog.csdn.net/u014723529/article/details/41958383
内容总结
以上是互联网集市为您收集整理的经典排序算法 - 归并排序Merge sort全部内容，希望文章能够帮你解决经典排序算法 - 归并排序Merge sort所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。