java归并排序如何实现

本篇内容主要讲解“java归并排序如何实现”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“java归并排序如何实现”吧!

归并排序相对于冒泡、插入、选择这三种排序时间复杂度是O(n2)来说适合大规模的数据排序，它的时间复杂度都是O(nlogn)。

它用到了分治的思想，把大问题分解成小问题，小问题再分，分而治之。

先来说说归并排序的思想：把要排序的数组从中间一分为二，分为左边和右边，然后左右分别排序，排好了之后再合并到一起(如果左右两边还能分继续一分为二，递归思想)这样就排好了！是不是感觉挺简单的？

来看一下图

上代码！我们利用递归来实现归并排序

代码关键点就是,recursion这个递归，就是把数组一分为二，然后排序！

merge方法的思路就是申请一个左边数组和右边数组一样长度的空数组用来存放结果，然后搞了两个游标i和j分别指向左数组和右数组，对比left[i]和right[j],哪个小就放入result中，然后对应的游标+1。循环结束之后，再把剩余的没塞入result的数据塞入result。这样就大功告成了！

归并排序的时间复杂度是O(nlogn)，并且从代码可以看left[i]小于等于right[j]的时候是塞入result所以它是稳定的排序！

例如[3,2,2,3]。当分为left和right之后并且内部排序之后是left[2,3]，right[2,3]。这时候还没破坏两个2直接的顺序，之后合并还是left的2先塞入result,所以是稳定的！

但是归并有一个不好点它不是原地排序，可以看到它需要额外的数组空间存放排序之后的结果。它的空间复杂度是O(n)。

到此，相信大家对“java归并排序如何实现”有了更深的了解，不妨来实际操作一番吧！这里是亿速云网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！