内容简介：合并排序算法是一种分而治之的算法。在分而治之的范式中，一个问题被分解成较小的问题，其中每个小问题仍然保留着大问题的所有属性——大小除外。为了解决原始问题，每个部分都是单独解决的，然后这些部分又合并在一起。例如，假设您必须使用冒泡排序算法对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部分课程，它以非常好的方式解释了键排序和搜索算法。 它还包括基本数据结构，如链表，数组，哈希表，二叉树等。
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
- git 的合并原理（递归三路合并算法）
- 算法 - 合并若干有序文件
- 让我们一起啃算法----合并两个有序数组
- 让我们一起啃算法----合并两个有序链表
- Hive集群合并之应用端的负载均衡算法
- LeetCode算法系列.0023_合并K个排序链表
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Programming in Haskell
Graham Hutton / Cambridge University Press / 2007-1-18 / GBP 34.99
Haskell is one of the leading languages for teaching functional programming, enabling students to write simpler and cleaner code, and to learn how to structure and reason about programs. This introduc......一起来看看 《Programming in Haskell》 这本书的介绍吧!
