为什么使用归并排序?
java中的Arrays.sort(Object[] o)是对数组进行排序,它使用的是归并排序的方式,
快速排序要比归并排序更快一些,但为什么使用归并排序了?原因是归并排序是一种稳定的排序
方式,即归并排序不交换相同的元素,这就意味着,在按一种方式排序后同时可以按另外一种
方式进行排序。比如员工可以首先按工资排序,然后按名字排序,一种排序不会打乱另一种排序
的顺序。
下面分析下sort方法的简化版:
/**
* 归并排序 (递归实现)
* 前提: 每个元素要有可比性,这里元素必须实现Comparable接口。
* 基本原理为:1.拆分 假设有N个元素的列表,首先把它拆分成2个或2个
* 以上的元素组成的新的列表(这里我的新列表长度不超过3),分别对对它们进行排序。
* 2.归并。把所有的排好序的子类表两两归并,如此重复,直到归并成一个含N个
* 元素的有序列表为止
* 图解:(大于3就继续分解)
* 大于3 8 7 6 5 4 3 2 1
* 分|解
* |
* 大于3 8 7 6 5 4 3 2 1
* 分|解 分|解
* | |
* 小于 3 8 7 6 5 4 3 2 1
* 排序 7 8 5 6 3 4 1 2
* 归并 | |
* 7 8 5 6 3 4 1 2
* | |
* 顺序保存 5 6 7 8 1 2 3 4
* |
* 归并 5 6 7 8 1 2 3 4
* |
* 顺序保存 1 2 3 4 5 6 7 8
* @param src 临时中间数组,它是目标数组的拷贝
* @param target 目标排序数组
* @param low 需排序的起始索引
* @param high 需排序的结束索引
*
*/
public static void mergeSort(Object[] src,Object[] dest,int low,int high){
int length = high - low;
if(length < 3 ){ //对长度小于3的列表排序
//排序方法一:起泡排序(大数沉底)
// for(int i=low;i<high-1;i++){
// for(int j=low;j<high-1-i+low;j++){
// if(((Comparable) dest[j]).compareTo(dest[j+1]) > 0){
// swap(dest, j, j+1);
// }
// }
// }
//排序方法二:这是起泡排序的一种变体(小数上浮)
for (int i = low; i < high; i++){
for (int j = i; j > low ; j--){
if(((Comparable) dest[j - 1]).compareTo(dest[j]) > 0){
swap(dest, j-1, j);
}
}
}
return;
}
int mid = (high + low)/2; //拆分
mergeSort(dest, src, low, mid); //递归,可能会继续拆分(那么必然继续合并)
mergeSort(dest, src, mid, high);
//开始归并,方法一
// for(int i=low,p=low,q=mid;i<high;i++){
// //第一个条件时为了添加剩余的值
// if(q >= high || (p < mid &&((Comparable) src[p]).compareTo(src[q]) <= 0)){
// dest[i] = src[p++];
// }else{
// dest[i] = src[q++];
// }
// }
//开始归并,方法二
int i = low;
int p = low; //第一个列表指针
int q = mid; //第二个列表指针
while(p < mid && q <high){
if(((Comparable) src[p]).compareTo(src[q]) <= 0){
dest[i++] = src[p++];
}else{
dest[i++] = src[q++];
}
}
//添加剩余的值
while(p < mid && i<high){
dest[i++] = src[p++];
}
while(q < high && i<high){
dest[i++] = src[q++];
}
private static void swap(Object[] x, int a, int b) {
Object t = x[a];
x[a] = x[b];
x[b] = t;
}
}
递归形式的算法在形式上比较简洁,但实用性不够好。
下面讲讲归并排序的非递归实现
public class MergeDemo{
public static void main(String[] args) {
String[] a= {"9","8","7","6","5","4","3","2","1"};
Object[] aux = (Object[])a.clone();
mergeSort(aux, a);
for(int i=0;i<a.length;i++){
System.out.println(a[i]);
}
}
//每个拆分的列表元素个数<=3
private static final int INSERTIONSORT_THRESHOLD = 3;
/**
*
* 归并排序(非递归实现)
*/
public static void mergeSort(Object[] src,Object[] dest){
int spreCount = INSERTIONSORT_THRESHOLD;
int low,mid,high;
int len = src.length;
if(len <= INSERTIONSORT_THRESHOLD*2){ //如果只能划分为两组,直接排序
sort(dest,0,len);
return;
}
while(spreCount < len){
for(int i=0;i<len;i=high){ //依次排序归并相邻两个列表
low = i;
high = low + spreCount * 2 ;
mid = low + spreCount;
if(high >= len){
high = len;
}
int l = high - low;
if(l <= INSERTIONSORT_THRESHOLD){
sort(src,low,high);
break;
}
if(spreCount == 3){ //所有拆分的列表只进行一次排序
sort(dest,low,mid);
sort(dest,mid,high);
}
if(l == len) //最后一次归并把src有次序的赋给dest
Merge(src,dest,low,mid,high);
else
Merge(dest,src,low,mid,high);
}
spreCount *= 2;
}
}
//对拆分的每个列表进行排序
private static void sort(Object[] dest,int low,int high){
for (int i = low; i < high; i++){
for (int j = i; j > low ; j--){
if(((Comparable) dest[j - 1]).compareTo(dest[j]) > 0){
swap(dest, j-1, j);
}
}
}
}
//归并相邻两个列表并保存在dest中
private static void Merge(Object[] src, Object[] dest, int low, int mid,
int high) {
int i = low;
int p = low; //第一个列表指针
int q = mid; //第二个列表指针
while(p < mid && q <high){
if(((Comparable) src[p]).compareTo(src[q]) <= 0){
dest[i++] = src[p++];
}else{
dest[i++] = src[q++];
}
}
//添加剩余的值
while(p < mid && i<high){
dest[i++] = src[p++];
}
while(q < high && i<high){
dest[i++] = src[q++];
}
}
private static void swap(Object[] x, int a, int b) {
Object t = x[a];
x[a] = x[b];
x[b] = t;
}
}
分享到:
相关推荐
java 实现归并排序,有代码实现,复杂度分析,基本步骤,适合初学者吧,
主要介绍了java 中归并排序算法详解的相关资料,归并排序算法又称为合并排序算法,是一种时间复杂度为O(N logN)的排序算法,因而其在平常生活工作中应用非常广泛,需要的朋友可以参考下
实现归并排序的一个类
使用Java实现简单的归并排序算法,给大家提供一个参考。
该资源提供了一份全面的指南,介绍了如何在Java中实现归并排序。文档中涵盖了归并排序的基本概念,包括如何对数组进行排序以及如何在Java中实现归并排序。此外,文档还包括一个逐步指南,介绍如何在Java中实现归并...
归并排序 在排序前,先建好一个长度等于原数组长度的临时数组
Java实现归并排序.rar
一年前做的排序动画,归并排序动画一直未完成,今天完成了,与大家共享
在Java实现中,归并排序通过递归调用mergeSortHelper方法将数组划分为更小的子数组,并在最后使用merge方法将有序子数组合并成一个完整的数组。归并排序虽然需要额外的空间来存储临时数组,但其稳定的性能和可并行化...
java归并外排序
java快速排序 归并排序 冒泡排序 选择排序
利用分治法思想实现归并排序,Java语言描述。
给初学者学习算法用,用java实现的排序算法,包括二路归并和插入排序。
用java语言实现冒泡排序、插入排序、堆排序、快速排序、归并排序、希尔排序、桶排序,并且对各种排序算法进行性能的比较。
JAVA排序大全 冒泡 快速 选择 归并排序
这是关于归并排序的demo,里面有递归版和非递归版的实现
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
mergeSort 方法实现了归并排序算法。它使用递归的方式将数组不断划分为更小的子数组,直到每个子数组只有一个元素,然后再依次将这些子数组进行合并,从而实现排序。 merge 方法用于合并两个有序子数组。它借助两个...
用ArrayList实现的排序算法,希望对有需要的同学有帮助,如有错误请指出。JDK版本为1.7
自动生成500个随机数,然后对这500个随机数进行归并排序