java 归并排序

最近看了个讲解归并排序的视频,是用C语言实现的。我想用java再实现一遍,加深印象,相当于做个笔记。

感觉这个系列的视频做得很好,讲得非常详细,有机会我会逐一实现视频中的代码。

参考:http://www.bilibili.com/video/av9982752/

 

一、实现过程

(1)使用分治的思想,把大的数组拆分成两个较小的数组

MergeSort.java

运行结果为:

至此,可以根据l、m、r调整两个较小的数组。

通过两个较小的数组的相互比较,可以得到排序结果。

(2)两个数组中的元素相互比较,进行初步排序

MergeSort.java

运行结果为:

可喜可贺,归并排序已经搞定了!

有人会说:“你这完全就是诈和啊!你给的数组{ 2, 8, 9, 10, 4, 5, 6, 7 }是特殊情况,分成两个较小数组时,刚好就是有序的!”

没错,如果把数组改成乱序的,比如{ 5, 4, 8, 7, 9, 6, 2, 10 },结果就变成了:

这说明程序依然是不完整的。那么接下来怎么办?

(3)使用递归,改进排序

我的思路是这样的:

首先要知道,我们无法保证某个数组中的元素是有序的。所以我们把数组拆开,得到更小的数组,做归并排序。

拆开后的数组还是不能保证有序,那么我们就继续拆开,得到更小的数组,再做归并排序。

如果把原始数组不断的拆开,不断地做归并排序,最后可以得到很多非常小的数组。

当然,拆分是有极限的。拆分到最后,如果数组中只有一个元素,当然无法继续拆分下去,在此同时,我们也能保证此处的元素是有序的(容量为2的数组拆分成两个容量为1的小数组,两个数组中唯一的元素进行大小比较,结果绝对是有序的)。

所以,我们要做的就是写个递归,不断地拆分数组,做归并排序,直到所有元素都有序为止。

那么问题来了,既然要递归,我们什么时候停下来?

当一个数组不能再拆分了,就可以停下来了(只有一个元素,无法做拆分比较)。

MergeSort.java

结果为:

数次递归后,可以保证数据是有序的。

二、总结

从宏观上看不一定好理解,所以我推荐去看视频,讲得很清楚。

发表评论

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