归并排序
归并排序是另一类不同的排序方法,所谓归并,就是把两个或者两个以上的有序表合并成一个新的有序表的过程。
归并排序的基本思想:
将一个含有n个序列的有序表看成是n个长度为1的有序表,然后两两归并,得到[n/2]个长度为2的有序表,然后再两两归并,直到得到一个长度为n的有序表为止。
下面是归并排序的一个简单的例子:
初始值 【49】 【38】 【65】 【97】 【76】 【13】 【27】
看成由长度为1的7个子序列组成
第一次合并之后 【38 49】 【65 97】 【13 76】 【27】
看成由长度为1或2的4个子序列组成
第二次合并之后 【38 49 65 97】 【13 27 76】
看成由长度为4或3的2个子序列组成
第三次合并之后 【13 27 38 49 65 76 97】
归并排序的JAVA实现:
public class MergeSort {
/**
* 归并排序 先将初始的序列表看成是n个长度为1的有序表 (1)定义指针i,指向第一个序列表的第一个元素
* (2)定义指针j,指向第二个序列表的第一个元素 (3)比较i,j指向的元素大小,若前者大,将后者插入到新表中 否则,把前者插入到后表中
* (4)直到取完第一个序列表或者第二个序列表为止
*
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] num = { 51, 38, 49, 27, 62, 05, 16 };
int[] num1 = new int[7];
num = mergesort(num, 0, num.length - 1, num1);
for (int i : num) {
System.out.print(i + " ");
}
}
private static int[] mergesort(int[] num, int s, int t, int[] num1) {
int m;
int[] num2 = new int[t + 1];
if (s == t)
num1[s] = num[s];
else {
m = (s + t) / 2;
mergesort(num, s, m, num2);//左半部分递归调用
mergesort(num, m + 1, t, num2);//右半部分递归调用
merg(num2, s, m, t, num1);// 由num2去归并,返回的值放到num1中,num1赋新值,其实就是更新num2,然后让num2再去归并,返回新的num1
}
return num1;
}
//有序表的合并
private static void merg(int[] num, int l, int m, int n, int[] num1) {
System.out.print("l=" + l + " m=" + m + " n=" + n);
System.out.println();
int i, j, k;
i = l;
j = m + 1;
k = l;
while (i <= m && j <= n) {
if (num[i] < num[j])
num1[k++] = num[i++];
else {
num1[k++] = num[j++];
}
}
while (i <= m) {
num1[k++] = num[i++];
}
while (j <= n) {
num1[k++] = num[j++];
}
}
}
性能分析:
时间复杂度:
由于归并的趟数,等于树的高度Logn,每趟归并需要移动记录n次,因此归并排序的时间复杂度为nlogn.
空间复杂度:
从上面的算法可以看出,需要一个辅助空间num2,其长度等于n,所以归并排序的辅助空间为O(n).
稳定性:
归并排序不涉及到交换,因此它是一种稳定的排序算法。
归并排序是典型的用空间去换取时间,它的时间开销比简单排序要优越,但需要与序列等长的辅助空间。
分享到:
相关推荐
C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序
自己编写的基于java的快速排序和归并算法
C++排序算法之归并排序源码
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
各种常用c++排序算法,包括插入排序、冒泡排序、选择排序、快速排序、归并排序、希尔排序等
主要介绍了C语言实现排序算法之归并排序,对归并排序的原理及实现过程做了非常详细的解读,需要的朋友可以参考下
详解Java常用排序算法-归并排序
根据算法导论实现的归并排序算法
自动生成500个随机数,然后对这500个随机数进行归并排序
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
易语言归并排序算法源码,归并排序算法,归并排序,子程序_有序数组合并
排序算法-归并排序详细讲解(MergeSort)
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
本人自己写的一些排序算法,这是系列1归并排序算法实现,
C++实现希尔、快速、堆排序、归并排序算法,一些中文注释可能成乱码了,但是不影响代码执行。
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
基于python的排序算法-归并排序Merge Sort
快速排序、归并排序、基数排序等排序算法比较,比较时间性能,采用C++语言实现。。。
C语言二路归并排序算法, 写了个二路归并的归并排序小代码,直接贴上来
归并排序算法,有程序和复杂性分析,还有解释,挺清楚的,很有用