package algorithm.sort;
/**
* 合并(归并)排序:按照分治模式,操作如下:
* 分解:将n个元素分成各含n/2个元素的子序列
* 解决:用合并排序法对两个子序列递归排序
* 合并:合并两个已经排序的子序列已得到排序结果
* @author Administrator
*/
public class MergeSort {
/**
* 合并排序的关键在于合并两个已经排好序的子序列
* a[from, mid],a[mid+a, end]已排好序,合并成已排序的数组代替a[from, end]
* @param a
* @param from
* @param end
* @param mid
*/
//方法一:在过程中利用最大值作为哨兵值,来避免检查每个子序列是否为空
//一旦两个子序列都出现这个哨兵值,说明所有的值都已经合并,复制回数组a
public void merge1(int[] a, int from, int mid, int end) {
//左右数组,且每个数组长度+1,为了存放哨兵值
int nl = mid - from + 1;
int nr = end - mid;
int[] left = new int[nl + 1];
int[] right = new int[nr + 1];
System.arraycopy(a, from, left, 0, nl);
System.arraycopy(a, mid+1, right, 0, nr);
//哨兵值
left[nl] = Integer.MAX_VALUE;
right[nr] = Integer.MAX_VALUE;
int i = 0; //控制左边数组
int j = 0; //控制右边数组
//从左右两个临时数组中各取一个数比较,将较小的一个数复制回数组
for (int k = from; k <= end; k++) {
if (left[i] <= right[j]) {
//哨兵值在这里得到体现,如果其中一个复制完,就会一直复制另外一个
a[k] = left[i];
i++; //接着下一个
} else {
a[k] = right[j];
j++;
}
}
}
//方法二:不使用哨兵值,一旦其中的一个子序列所有元素都被复制回数组a,就立刻停止
//再将另外一个子序列中剩余的元素复制回数组a即可
public void merge2(int[] a, int from, int mid, int end) {
//左右数组
int nl = mid - from + 1;
int nr = end - mid;
int[] left = new int[nl];
int[] right = new int[nr];
System.arraycopy(a, from, left, 0, nl);
System.arraycopy(a, mid+1, right, 0, nr);
int i=0, j=0, k=from;
//一旦其中一个子序列所有元素复制完就立刻停止
while(i < nl & j < nr) {
if(left[i] <= right[j]) {
a[k++] = left[i++];
} else {
a[k++] = right[j++];
}
}
//复制剩余的元素
for(; i < nl; i++){
a[k++] = left[i];
}
for(; j < nr; j++) {
a[k++] = right[j];
}
}
//递归划分数组
public void mergeSort(int[] a, int from, int end) {
//单个元素视为已排好序的
if(from < end) {
//从中间划分数组
int mid = (end + from) / 2;
//递归划分数组
mergeSort(a, from, mid);
mergeSort(a, mid+1, end);
merge2(a, from, mid, end);
}
}
//对整个数组排序
public void mergeSort(int[] a) {
mergeSort(a, 0, a.length-1);
}
//打印数组
public void printArr(String str, int[] a) {
System.out.print(str + "\t");
for(int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.println();
}
//测试数据
public static void main(String[] args) {
MergeSort ms = new MergeSort();
int[] a = {1,4,3,7,5,8,0};
ms.printArr("原始数组为:", a);
ms.mergeSort(a);
ms.printArr("合并排序后:", a);
}
}
分享到:
相关推荐
自动生成500个随机数,然后对这500个随机数进行归并排序
归并排序 在排序前,先建好一个长度等于原数组长度的临时数组
java代码-使用java解决java排序之-归并排序的问题的源代码 ——学习参考资料:仅用于个人学习使用!
算法-归并排序(java)(csdn)————程序
(10)数据结构之红黑树(三)——删除操作 (11)排序算法(一)——冒泡排序及改进 (12)排序算法(二)——选择排序及改进 (13)排序算法(三)——插入排序及改进 (14)排序算法(四)——归并排序与递归...
NULL 博文链接:https://yuan.iteye.com/blog/308778
排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法,分支限界...
小白日记之八种排序算法——八种排序算法:冒泡排序、选择排序、插入排序、希尔排序、基数排序、堆排序、归并排序、快排
本文件讲了十种JAVA排序方法(冒泡(Bubble)排序——相邻交换 、选择排序——每次最小/大排在相应的位置 、插入排序——将下一个插入已排好的序列中 、壳(Shell)排序——缩小增量 、归并排序 、快速排序 、堆排序 ...
排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法,分支限界...
排序7.1 预备知识7.2 插入排序7.2.1 算法7.2.2 插入排序的分析7.3 一些简单排序算法的下界7.4 希尔排序7.5 堆排序7.6 归并排序7.7 快速排序7.7.1 选取枢纽元7.7.2 分割策略7.7.3 小数组7.7.4 实际的快速排序例程...
排序7.1 预备知识7.2 插入排序7.2.1 算法7.2.2 插入排序的分析7.3 一些简单排序算法的下界7.4 希尔排序7.5 堆排序7.6 归并排序7.7 快速排序7.7.1 选取枢纽元7.7.2 分割策略7.7.3 小数组7.7.4 实际的快速排序例程...
7.6 归并排序 7.7 快速排序 7.7.1 选取枢纽元 7.7.2 分割策略 7.7.3 小数组 7.7.4 实际的快速排序例程 7.7.5 快速排序的分析 7.7.6 选择问题的线性期望时间算法 7.8 排序算法的一般下界 7.9 桶式排序 7.10 外部排序 ...
排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法,分支限界...
排序7.1 预备知识7.2 插入排序7.2.1 算法7.2.2 插入排序的分析7.3 一些简单排序算法的下界7.4 希尔排序7.5 堆排序7.6 归并排序7.7 快速排序7.7.1 选取枢纽元7.7.2 分割策略7.7.3 小数组7.7.4 实际的快速排序例程...
练习 参考文献第7章 排序 7.1 预备知识 7.2 插入排序 7.2.1 算法 7.2.2 插入排序的分析 7.3 一些简单排序算法的下界 7.4 希尔排序 7.5 堆排序 7.6 归并排序 7.7 快速排序 7.7.1 选取枢纽元 ...
练习 参考文献第7章 排序 7.1 预备知识 7.2 插入排序 7.2.1 算法 7.2.2 插入排序的分析 7.3 一些简单排序算法的下界 7.4 希尔排序 7.5 堆排序 7.6 归并排序 7.7 快速排序 7.7.1 选取枢纽元 ...
- 归并排序 - 快速排序 ###第八章 -不相交集 ###第九章 -邻接表(Versioni 1,2) -拓扑排序(Versioni 1,2) -单源最短路径算法 -最大网络流 -最小生成树 -深度优先搜索 -双连通性 -欧拉回路 ###第十章 -分治算法:最近...
关于java程序员发展需要学习的路线整理集合 技术 应用技术 计算机基础知识 cpu mem disk net 线程,进程 第三方库 poi Jsoup zxing Gson 数据结构 树 栈 链表 队列 图 操作系统 linux 代码控制...