Java归并排序法

许多数据存储在计算机中，这些数据存储时有一定的排序，在使用和查询时也有排序，会有一定的排序方法来实现计算机的有序数据，java合并排序法就是其中之一，今天是对的java排序不熟悉的java零基础介绍新手相信通过学习以下知识，java归并排序法的概念和原理一定能够理解java归并排序法的相关内容。

假设有两个朋友想在一个数组中对数值进行排序，一种方法是将数组分成两个相等的部分，每个人都对其中一半进行排序，很容易将两个排序数组结合起来，形成最终结果，这是定义java归并排序法，这种有序值的交叉称为合并（merge)。

很容易看出，至少需要合并O(n）时间，因为每个值都必须移动到最终结果。n -在一次比较之内，合并将不可避免地结束。由于每个n-1次比较（以及隐藏的数据移动）最多需要常数时间，因此合并的时间效率不会比线性时间差。

当然，有些地方很难处理并购操作。例如，一半数据中的所有值都可能小于另一半。以下是java归并排序法代码的时间复杂度仍然很复杂O(n):

这个代码相当通用，但有些很难理解。我们假设两个列表中的值分别在两个数组中temp中位置较低的一半和data中位置较高的一半(下图)a） 。第一个循环比较两个列表中剩余元素中的第一个，以确定哪一个应该首先复制到结果列表中（下图）b）。这个过程一直持续到一个列表为空(下图)c） 如果 data 是空列表 ，将temp中剩余的数据传输到结果列表(下图)d）； 如果temp是空列表，然后data 剩下的值已经在正确的位置了。

上图:两者分别包含:将六个元素列表合并的四个阶段(阴影中的元素是参与排序的值)：(a）数据的原始位置；（b）多个值的合并；（c）列表为空的情况；（d）最终结果

回顾数据排名中的两个朋友，我们注意到每个人都面临着在两个列表合并之前对一半数据进行排名的问题。他们应该怎么做？如果一组数据中只有不到两个值，则已排序 。否则，每个人都应该把自己一半的数据（整个数据的四分之一）交给另一个人。一旦这个小规模的排名结束 ，四分之一的数据被合并，一半的数据被排序，两半的数据被合并，形成最终完整的排序数据。这是一种新的排序方法，称为合并排序（mergsort），对一组数据进行分割、排序和重组。下图描述了java合并排序法的逻辑 “阶段”。

请注意，这种排序方法需要一个临时数组来支持合并。这个临时数组只能一次使用一个合并过程。因此，它一次分配存储空间，然后在排序完成后回收。我们使用一个包装过程来隐藏这些详细信息，即数组分配存储空间，并调用递归排序过程。

显然，分割的深度取决于n可以平分的次数，保持每个部分的数据量仍然是一个等于1的数字，或者更大：log2 n 。每次分割，每个值都必须合并到相应的子数组中。在每个逻辑层面上，O都需要在所有合并中(n）次比较。因为一共有 log2n层次，O并排序执行一次(nlogn）工作单位。

java合并排序的一个缺点是，如果没有大量的额外存储空间，就很难对两组数据进行排序。如果我们可以避免使用这些额外的存储空间，而比较次数或数据的移动增加很小，这将是一个非常好的排序方法。

对所有存储在高速存储器中的大数据集进行排序，java合并排序法是一种常用的技术。数据存储在合并的临时文件中。当递归过程将集合分成大小可操作的子集时，如有必要，也可使用其他技术分别对它们进行排序。

希望通过这篇文章介绍可以让大家理解java归并排序法的概念和原理，使java归并排序法在编写程序时能够熟练地处理数据。