并归排序:
将两个或两个以上的有序数组组合成一个新的有序数组,叫并归排序
排序过程
1、 设初始数组有n个数据,则可看成n个有序的子数组, 每个子数组长度为1;
2、 两两合并,得到n/2或n/2+1 个长度为2 或1 的有序子数组;
3、 再两两合并,…… 如此重复,直至得到一个长度为n 的有序数组为止。
下面是归并排序的一个简单的例子:
初始值 【49】 【38】 【65】 【97】 【76】 【13】 【27】
public class MergeSort {
public static void sort(int[] arr) {
//创建临时数组
int[] tempArr =new int[arr.length];
msort(arr, tempArr, 0, arr.length);
}
private static void msort(int[] arr, int[] tempArr, int first,int last) {
if (first+1 < last) {
int midpt = (last + first) / 2;
msort(arr, tempArr, first, midpt);
msort(arr, tempArr, midpt, last);
if (arr[midpt - 1]<=arr[midpt])//如果前半部分与后半部分正好形成了顺序
return;
int indexA, indexB, indexC;//前半部分的索引,后半部分的索引,临时数组的索引
indexA = first;
indexB = midpt;
indexC = first;
while (indexA < midpt && indexB < last) {
if (arr[indexA]<arr[indexB]) {
tempArr[indexC] = arr[indexA]; //copyto tempArr
indexA++;
} else {
tempArr[indexC] = arr[indexB]; //copyto tempArr
indexB++;
}
indexC++;
}
//copy the tail of the sublist that is not exhausted
while (indexA < midpt) {
tempArr[indexC++] = arr[indexA++];
} while (indexB < last) {
tempArr[indexC++] = arr[indexB++];
}
将临时数组的所有元素复制到原数组
for (int i = first; i < last; i++)
arr[i] = tempArr[i];
}
}
public static void main(String[] args){
int a[]={100,7,10,19,56,25,12,7,17,21,-1,30,48};
sort(a);
for(int i:a)
System.out.print(i+",");
}
}
- 大小: 37.1 KB
分享到:
相关推荐
实现归并排序的一个类
利用分治法思想实现归并排序,Java语言描述。
java 实现归并排序,有代码实现,复杂度分析,基本步骤,适合初学者吧,
使用Java实现简单的归并排序算法,给大家提供一个参考。
自然合并的核心主要是一个Pass函数,这个函数中设置了一个array数组,来存放每一组有序元素的起始元素的下标,最后再将最后一个元素的下标+1存放为array数组的最后一个元素,这样,在后面的合并实现中会显现出这样记录的...
这是关于归并排序的demo,里面有递归版和非递归版的实现
NULL 博文链接:https://yeelor.iteye.com/blog/1964843
该资源提供了一份全面的指南,介绍了如何在Java中实现归并排序。文档中涵盖了归并排序的基本概念,包括如何对数组进行排序以及如何在Java中实现归并排序。此外,文档还包括一个逐步指南,介绍如何在Java中实现归并...
外排序--基于败者树的多路归并排序算法的java实现
冒泡排序 简单选择排序 直接插入排序 希尔排序 归并排序 快速排序等排序方法,使用java详细代码 附注释,清晰明白
JAVA排序大全 冒泡 快速 选择 归并排序
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
归并排序 在排序前,先建好一个长度等于原数组长度的临时数组
给初学者学习算法用,用java实现的排序算法,包括二路归并和插入排序。
自动生成500个随机数,然后对这500个随机数进行归并排序
一年前做的排序动画,归并排序动画一直未完成,今天完成了,与大家共享
归并排序的链表实现 随机生成实验数据,可以统计算法运行时间
一个Java小程序,利用递归思想实现的归并排序算法。其中有两个类,排序数据是写死在main方法中的。
JavaSwing写的归并排序动画,我一年前写的排序动画,里面的归并排序现在终于完成了,拿出来与大家分享分享