归并排序的实现(排序算法c语言描述)

归并排序法是将两个(或两个以上)有序表合并成一个新的有序表,是建立在归并操作上的一种有效的排序算法,具体是把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。该算法是采用分治法的一个非常典型的应用。所以归并排序的核心在于先分解,再合并。
基本思路:
将数组分成二组A,B,如果这二组组内的数据都是有序的,那么就可以很方便的将这二组数据进行排序。为了让这两组数据是有序的,可以继续将A,B组各自再分成二组。依次类推,当分出来的小组只有一个数据时,可以认为这个小组组内已经达到了有序,然后再合并相邻的二个小组就可以了。这样就实现了先递归的分解数列,再合并数列就完成了归并排序。
具体操作:
1) 将n个元素分成各含n/2个元素的子序列
2)用归并排序法对这两个子序列递归地排序
3)合并这两个已经排序好的子序列得到排序结果

我们通过一个图像来形象的理解一下:

代码:
下面,我们先看看实现有序数组的合并:

我们继续看归并排序的实现:

测试程序:

作者:u010927811 发表于2013-8-14 16:06:32 原文链接
阅读:122 评论:0 查看评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">