一. 概念
归并的含义是将两个或两个以上的有序表合并成一个新的有序表。大体分成，两路归并排序，和多路归并排序。用于内排序，和外排序。(此篇主要介绍两路内排序)
二. 归并排序的思路
1. 拆分:
把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.
2. 递归:
对每个子序列分别调用归并排序, 进行递归操作.
3.合并
合并两个排好序的子序列,生成排序结果。举个例子：
下列是一组待排序的数列: (下面列举的是从小到大排列)
初始值：[1, 17, 13, 5, 11, 7, 3, 15, 9]
首先拆分,
[1] [17] [13] [5] [11] [7] [3] [15] [9]
第一次合并：
每个数组里面的元素按照大到小排序下, 如果数组总元素是奇数的，那么暂时排在第一个数组的后面，如下：
[1, 17] [13] [11, 5] [3, 7] [9, 15]
下面依次排序,
[1, 13, 17] [11, 5] [3, 7] [9, 15]
[1, 5, 11, 13, 17] [3, 7, 9, 15]
[1, 3, 5, 7, 9, 11, 13, 15, 17]
三，代码
package practice;
public class myMergeSort {
static int number = 0;
public static void main(String[] args) {
int[] a = { 1, 17, 13, 5, 11, 7, 3, 15, 9};
printArray("排序前：", a);
MergeSort(a);
printArray("排序后：", a);
}
private static void printArray(String pre, int[] a) {
System.out.print(pre + "\n");
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + "\t");
System.out.println();
}
private static void MergeSort(int[] a) {
// TODO Auto-generated method stub
System.out.println("开始排序");
Sort(a, 0, a.length - 1);
}
private static void Sort(int[] a, int left, int right) {
if (left >= right)
return;
int mid = (left + right) / 2;
// 二路归并排序里面有两个Sort，多路归并排序里面写多个Sort就可以了
Sort(a, left, mid);
Sort(a, mid + 1, right);
merge(a, left, mid, right);
}
private static void merge(int[] a, int left, int mid, int right) {
int[] tmp = new int[a.length];
int r1 = mid + 1;
int tIndex = left;
int cIndex = left;
// 逐个归并
while (left <= mid && r1 <= right) {
if (a[left] <= a[r1])
tmp[tIndex++] = a[left++];
else
tmp[tIndex++] = a[r1++];
}
// 将左边剩余的归并
while (left <= mid) {
tmp[tIndex++] = a[left++];
}
// 将右边剩余的归并
while (r1 <= right) {
tmp[tIndex++] = a[r1++];
}
System.out.println("第" + (++number) + "趟排序:\t");
// TODO Auto-generated method stub
// 从临时数组拷贝到原数组
while (cIndex <= right) {
a[cIndex] = tmp[cIndex];
// 输出中间归并排序结果
System.out.print(a[cIndex] + "\t");
cIndex++;
}
System.out.println();
}
}
四， 运行结果
排序前：
1 17 13 5 11 7 3 15 9
开始排序
第1趟排序:
1 17
第2趟排序:
1 13 17
第3趟排序:
5 11
第4趟排序:
1 5 11 13 17
第5趟排序:
3 7
第6趟排序:
9 15
第7趟排序:
3 7 9 15
第8趟排序:
1 3 5 7 9 11 13 15 17
排序后：
1 3 5 7 9 11 13 15 17
五，算法分析
1.稳定性
归并排序是一种稳定的排序。
2.存储结构要求
可用顺序存储结构。也易于在链表上实现。
3.时间复杂度
对长度为n的文件，需进行 趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。
4.空间复杂度
需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。
注意：
若用单链表做存储结构，很容易给出就地的归并排序。
六，归并排序的优缺点
优点：
一, 归并排序的效率达到了巅峰：时间复杂度为O(nlogn)，这是基于比较的排序算法所能达到的最高境界
二, 归并排序是一种稳定的算法（即在排序过程中大小相同的元素能够保持排序前的顺序，3212升序排序结果是1223，排序前后两个2的顺序不变），这一点在某些场景下至关重要
三, 归并排序是最常用的外部排序方法（当待排序的记录放在外存上，内存装不下全部数据时，归并排序仍然适用，当然归并排序同样适用于内部排序...）
缺点：
归并排序需要O(n)的辅助空间，而与之效率相同的快排和堆排分别需要O(logn)和O(1)的辅助空间，在同类算法中归并排序的空间复杂度略高
网友评论