您的位置: 首页  >  文章  >  合并排序Java实现

合并排序Java实现

分类: 文章 • 2024-01-18 09:51:46

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

在Mergesort过程中，集合中的对象分为两个集合。要拆分集合，Mergesort将占据集合的中间位置，并将集合拆分为左侧和右侧。生成的集合再次通过Mergesort算法进行递归分割，直到它们分解为每个集合中的单个元素。

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

此过程创建已排序元素的集合（需要对所有元素进行排序的子集）。对于在第一步中获得的所有可用集合递归地完成该过程，即分割集合。

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

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

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

合并排序Java实现

合并排序算法

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

  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);

    }

}

 
输出：

输入数组：[2,6,3,5,1,1,8]
输出数组：[1,1,2,3,5,6,8]

输入数组：[12,16,333,50,1000,5,897,1,3,66,13]
输出数组：[1,3,5,12,13,16,50,66,333,897,1000]

何时使用合并排序

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

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

  2. 此外，您还可以在需要稳定排序时使用合并排序。这是合并排序的一个非常重要的特性。
  3. 在处理链表时，Mergesort更快。这是因为合并列表时可以轻松更改指针。它只需要通过列表一次（O（n））。
  4. 如果发生了大量并行化，那么并行化Mergesort比其他排序算法更简单。

这就是合并排序java教程。请在下面的评论部分中提出您的问题/疑问。

相关推荐