Java中的合并排序算法

栏目: 编程工具 · 发布时间: 5年前

内容简介:合并排序算法是一种分而治之的算法。在分而治之的范式中,一个问题被分解成较小的问题,其中每个小问题仍然保留着大问题的所有属性——大小除外。为了解决原始问题,每个部分都是单独解决的,然后这些部分又合并在一起。例如,假设您必须使用冒泡排序算法对200个元素的数组进行排序。因为选择排序需要O(n^2)时间,所以对数组进行排序大约需要40000个时间单位。现在想象一下,将数组拆分成十个相等的片段,并使用选择排序对每个片段进行单独排序。现在,每件物品的分类需要400个时间单位;总共10*400=4000。一旦每一部分被

合并 排序 算法是一种分而治之的算法。在分而治之的范式中,一个问题被分解成较小的问题,其中每个小问题仍然保留着大问题的所有属性——大小除外。为了解决原始问题,每个部分都是单独解决的,然后这些部分又合并在一起。例如,假设您必须使用冒泡 排序算法 对200个元素的数组进行排序。因为选择排序需要O(n^2)时间,所以对数组进行排序大约需要40000个时间单位。现在想象一下,将数组拆分成十个相等的片段,并使用选择排序对每个片段进行单独排序。现在,每件物品的分类需要400个时间单位;总共10*400=4000。

一旦每一部分被分类,将它们重新合并将需要大约200个时间单位;总计200+4000=4200。显然,4200比40000是一个显著的进步。

现在想想更大点。设想将原始数组分成两组,然后对它们进行排序。最后,对数组进行排序大约需要1000个时间单位。

这就是合并排序的工作原理。它使大数组的排序变得容易,因此适用于大整数和字符串数组。合并排序算法的时间复杂度在最佳、平均和最差情况下是相同的,等于O(n*log(n))。

顺便说一下,如果你对算法和数据结构很陌生,不熟悉Quas排序、二进制搜索、级搜索等基本排序和搜索算法,那么我建议你通过一个好的、全面的在线课程,比如数据结构和算法:用 Java 深入学习基本知识。

使用合并排序算法对数组进行排序:

您已经给出了一个无序的整数列表(或任何其他对象,例如字符串),您必须按其自然顺序重新排列整数或对象。

Sample Input: {80, 50, 30, 10, 90, 60, 0, 70, 40, 20, 5}

Sample Output: {0, 10, 20, 30, 40, 50, 50, 60, 70, 80, 90}

<b>import</b> java.util.Arrays;

<font><i>/*
 * Java Program to sort an integer array using merge sort algorithm.
 */</i></font><font>

<b>public</b> <b>class</b> Main {

  <b>public</b> <b>static</b> <b>void</b> main(String args) {

    System.out.println(</font><font>"mergesort"</font><font>);
    <b>int</b> input = { 87, 57, 370, 110, 90, 610, 02, 710, 140, 203, 150 };

    System.out.println(</font><font>"array before sorting"</font><font>);
    System.out.println(Arrays.toString(input));

    </font><font><i>// sorting array using MergeSort algorithm</i></font><font>
    mergesort(input);

    System.out.println(</font><font>"array after sorting using mergesort algorithm"</font><font>);
    System.out.println(Arrays.toString(input));

  }

  </font><font><i>/**
   * Java function to sort given array using merge sort algorithm
   * 
   * @param input
   */</i></font><font>
  <b>public</b> <b>static</b> <b>void</b> mergesort(<b>int</b> input) {
    mergesort(input, 0, input.length - 1);
  }

  </font><font><i>/**
   * A Java method to implement MergeSort algorithm using recursion
   * 
   * @param input
   *          , integer array to be sorted
   * @param start
   *          index of first element in array
   * @param end
   *          index of last element in array
   */</i></font><font>
  <b>private</b> <b>static</b> <b>void</b> mergesort(<b>int</b> input, <b>int</b> start, <b>int</b> end) {

    </font><font><i>// break problem into smaller structurally identical problems</i></font><font>
    <b>int</b> mid = (start + end) / 2;
    <b>if</b> (start < end) {
      mergesort(input, start, mid);
      mergesort(input, mid + 1, end);
    }

    </font><font><i>// merge solved pieces to get solution to original problem</i></font><font>
    <b>int</b> i = 0, first = start, last = mid + 1;
    <b>int</b> tmp = <b>new</b> <b>int</b>[end - start + 1];

    <b>while</b> (first <= mid && last <= end) {
      tmp[i++] = input[first] < input[last] ? input[first++] : input[last++];
    }
    <b>while</b> (first <= mid) {
      tmp[i++] = input[first++];
    }
    <b>while</b> (last <= end) {
      tmp[i++] = input[last++];
    }
    i = 0;
    <b>while</b> (start <= end) {
      input[start++] = tmp[i++];
    }
  }
}

Output
mergesort
array before sorting
<p>[87, 57, 370, 110, 90, 610, 2, 710, 140, 203, 150]
array after sorting using mergesort algorithm
<p>[2, 57, 87, 90, 110, 140, 150, 203, 370, 610, 710]
</font>

您可以看到该数组现已排序。 我们使用的算法是合并排序的递归实现,它也是一个稳定的排序算法。

无论如何,如果你还没有得到合并排序算法的工作原理,你还可以查看算法和数据结构 - 关于Pluralsight的第1部分和第2部分课程,它以非常好的方式解释了键排序和搜索算法。 它还包括基本数据结构,如链表,数组,哈希表,二叉树等。


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

白帽子讲Web安全(纪念版)

白帽子讲Web安全(纪念版)

吴翰清 / 电子工业出版社 / 2014-6 / 69.00元

互联网时代的数据安全与个人隐私受到前所未有的挑战,各种新奇的攻击技术层出不穷。如何才能更好地保护我们的数据?《白帽子讲Web 安全(纪念版)》将带你走进Web 安全的世界,让你了解Web 安全的方方面面。黑客不再神秘,攻击技术原来如此,小网站也能找到适合自己的安全道路。大公司如何做安全,为什么要选择这样的方案呢?在《白帽子讲Web 安全(纪念版)》中都能找到答案。详细的剖析,让你不仅能“知其然”,......一起来看看 《白帽子讲Web安全(纪念版)》 这本书的介绍吧!

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具