合并排序 Java 示例

在计算机科学中，合并排序（通常也拼写为 mergesort）是一种基于O(n log n) 比较的排序算法。大多数实现会生成一个稳定排序，这意味着该实现保留了排序输出中相等元素的输入顺序。 归并排序是一种分而治之的算法。分而治之算法将原始数据分成更小的数据集来解决问题。

在 Mergesort 过程中，集合中的对象被分成两个集合。为了拆分一个集合，Mergesort 将取集合的中间部分并将集合拆分为左右两部分。生成的集合再次通过 Mergesort 算法递归拆分，直到它们被分解为每个集合中的单个元素。

拆分每个集合后，mergesort 算法开始合并通过上述过程获得的所有集合。要合并两个集合，Mergesort 从每个集合的开头开始。它选择较小的对象并将该对象插入到新集合中。对于这个集合，它现在选择下一个元素，并通过一次比较每个集合中的一个元素来从两个集合中选择较小的元素。

此过程创建已排序元素的集合（需要排序的所有元素的子集）。这个过程是针对第一步获得的所有可用集合递归完成的，即拆分集合。

一旦两个集合中的所有元素都被插入到新集合中，Mergesort 就成功地对集合进行了排序。

为了避免创建过多的集合，通常只创建一个新集合，并将新集合和现有集合视为不同的集合。

为了更好地理解，请查看遵循上述方法的下图。

归并排序算法

从概念上讲，合并排序以递归方式按如下方式工作：

1. 将未排序的列表分成两个大约一半大小的子列表
2. 对两个子列表中的每一个进行排序
3. 将两个已排序的子列表合并回一个已排序的列表

合并排序示例

在下面的示例中，我们以表达方式实现了归并排序算法，以使其更易于理解。按照下面给定的合并排序代码中每个步骤/语句上方的注释进行操作。

import java.util.*;

public class MergerSort 
{
	public static void main(String[] args) 
	{
		//Unsorted array
		Integer[] a = { 2, 6, 3, 5, 1 };
		
		//Call merge sort
		mergeSort(a);
		
		//Check the output which is sorted array
		System.out.println(Arrays.toString(a));
	}

	@SuppressWarnings("rawtypes") 
	public static Comparable[] mergeSort(Comparable[] list) 
	{
		//If list is empty; no need to do anything
        if (list.length <= 1) {
            return list;
        }
        
        //Split the array in half in two parts
        Comparable[] first = new Comparable[list.length / 2];
        Comparable[] second = new Comparable[list.length - first.length];
        System.arraycopy(list, 0, first, 0, first.length);
        System.arraycopy(list, first.length, second, 0, second.length);
        
        //Sort each half recursively
        mergeSort(first);
        mergeSort(second);
        
        //Merge both halves together, overwriting to original array
        merge(first, second, list);
        return list;
    }
    
	@SuppressWarnings({ "rawtypes", "unchecked" }) 
    private static void merge(Comparable[] first, Comparable[] second, Comparable[] result) 
	{
        //Index Position in first array - starting with first element
        int iFirst = 0;
        
        //Index Position in second array - starting with first element
        int iSecond = 0;
        
        //Index Position in merged array - starting with first position
        int iMerged = 0;
        
        //Compare elements at iFirst and iSecond, 
        //and move smaller element at iMerged
        while (iFirst < first.length && iSecond < second.length) 
        {
            if (first[iFirst].compareTo(second[iSecond]) < 0) 
            {
                result[iMerged] = first[iFirst];
                iFirst++;
            } 
            else 
            {
                result[iMerged] = second[iSecond];
                iSecond++;
            }
            iMerged++;
        }
        //copy remaining elements from both halves - each half will have already sorted elements
        System.arraycopy(first, iFirst, result, iMerged, first.length - iFirst);
        System.arraycopy(second, iSecond, result, iMerged, second.length - iSecond);
    }
}

Output:

Input Array :  [ 2, 6, 3, 5, 1, 1, 8 ]
Output Array : [ 1, 1, 2, 3, 5, 6, 8 ]

Input Array :  [ 12, 16, 333, 50, 1000, 5, 897, 1, 3, 66, 13 ]
Output Array : [ 1, 3, 5, 12, 13, 16, 50, 66, 333, 897, 1000 ]

何时使用归并排序

1. 归并排序在数据结构不支持随机访问时使用，因为它适用于纯顺序访问（前向迭代器，而不是随机访问迭代器）。它还广泛用于外部排序，与顺序访问相比，随机访问可能非常非常昂贵。

   例如，当对不适合内存的文件进行排序时，您可以将其分解为适合内存的块，独立使用这些块进行排序，将每个文件写入一个文件，然后对生成的文件进行合并排序。

   p>
2. 此外，当您需要稳定排序时，您可以使用归并排序。这是归并排序的一个非常重要的特征。
3. 在处理链表时合并排序更快。这是因为在合并列表时可以很容易地更改指针。它只需要通过列表一次 (O(n))。
4. 如果发生大量并行化，那么并行化 Mergesort 比其他排序算法更简单。

这就是关于合并排序 Java 教程的全部内容。在下面的评论部分中将您的问题/疑问告诉我。

快乐学习！！

标签2： Algorithms Java Algorithms Java Sorting

地址：https://www.cundage.com/article/merge-sort-java-example.html