归并排序
归并排序是另一类不同的排序方法,所谓归并,就是把两个或者两个以上的有序表合并成一个新的有序表的过程。
归并排序的基本思想:
将一个含有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).
稳定性:
归并排序不涉及到交换,因此它是一种稳定的排序算法。
归并排序是典型的用空间去换取时间,它的时间开销比简单排序要优越,但需要与序列等长的辅助空间。
分享到:
相关推荐
java 实现归并排序,有代码实现,复杂度分析,基本步骤,适合初学者吧,
NULL 博文链接:https://yeelor.iteye.com/blog/1964843
实现归并排序的一个类
利用分治法思想实现归并排序,Java语言描述。
使用Java实现简单的归并排序算法,给大家提供一个参考。
外排序--基于败者树的多路归并排序算法的java实现
给初学者学习算法用,用java实现的排序算法,包括二路归并和插入排序。
自然合并的核心主要是一个Pass函数,这个函数中设置了一个array数组,来存放每一组有序元素的起始元素的下标,最后再将最后一个元素的下标+1存放为array数组的最后一个元素,这样,在后面的合并实现中会显现出这样记录的...
归并排序的java实现
该资源提供了一份全面的指南,介绍了如何在Java中实现归并排序。文档中涵盖了归并排序的基本概念,包括如何对数组进行排序以及如何在Java中实现归并排序。此外,文档还包括一个逐步指南,介绍如何在Java中实现归并...
归并排序的链表实现 随机生成实验数据,可以统计算法运行时间
这是关于归并排序的demo,里面有递归版和非递归版的实现
Java实现归并排序.rar
归并排序,消除递归归并排序,快排,Java实现
一个Java小程序,利用递归思想实现的归并排序算法。其中有两个类,排序数据是写死在main方法中的。
快速排序、归并排序、希尔排序、冒泡排序、选择排序、插入排序等8中排序方式原理分析java实现
JAVA排序大全 冒泡 快速 选择 归并排序
自动生成500个随机数,然后对这500个随机数进行归并排序
归并排序 在排序前,先建好一个长度等于原数组长度的临时数组
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht