文档章节

归并排序 -java实现

Amui
 Amui
发布于 2015/10/01 11:23
字数 469
阅读 8
收藏 0

归并排序将待排序的元素序列分成两个长度相等的子序列,为每一个子序列排序,然后再将它们合并成一个序列。

使用分治法的思想。Divid and Conquer

详细介绍看:http://www.cnblogs.com/jingmoxukong/p/4308823.html

public class MergeSort {
	//合并两个分组
	public static void Merge(int[] arr, int low, int mid, int high){
		int i = low;
		int j = mid + 1; 
		int k = 0;
		int[] arr2 = new int[high - low + 1];
		
		while(i <= mid && j <= high){
			if(arr[i] < arr[j]){
				arr2[k++] = arr[i++];
			}else{
				arr2[k++] = arr[j++];
			}
		}
		
		while(i <= mid){
			arr2[k++] = arr[i++];			
		}
		
		while(j <= high){
			arr2[k++] = arr[j++];
		}
		
		for(k = 0, i = low; i <= high; i++, k++){
			arr[i] = arr2[k];
		}
	}
	
	//划分
	public static void MergePass(int[] arr, int gap, int length){
		int i = 0;
		for(i = 0; i + 2 * gap -1 < length; i = i + 2 * gap){
			Merge(arr, i, i + gap -1, i + 2 * gap -1);
		}
		
		//余下两个分组,其后一个长度小于gap
		if(i + gap -1 < length){
			Merge(arr, i, i + gap -1, length-1);
		}
	}
	
	public static void sort(int[] arr){
		for(int gap = 1; gap < arr.length; gap = gap * 2){
			MergePass(arr, gap, arr.length);
		}
	}
	
	public static void main(String[] args){
		int[] arr = {9, 8, 7, 13, 21, 1, 17, 6};
		System.out.println("排序前:");
		for(int i = 0; i < arr.length; i++){
			System.out.print(arr[i] + ",");
		}
		
		sort(arr);
		
		System.out.println("\n排序后:");
		for(int i = 0; i < arr.length; i++){
			System.out.print(arr[i] + ",");
		}
	}
}


归并排序:

使用递归的方式:

public class MergeSort2 {
	//合并两个分组
	public static void Merge(int[] arr, int low, int mid, int high){
		int i = low;
		int j = mid + 1; 
		int k = 0;
		int[] arr2 = new int[high - low + 1];
		
		while(i <= mid && j <= high){
			if(arr[i] < arr[j]){
				arr2[k++] = arr[i++];
			}else{
				arr2[k++] = arr[j++];
			}
		}
		
		while(i <= mid){
			arr2[k++] = arr[i++];			
		}
		
		while(j <= high){
			arr2[k++] = arr[j++];
		}
		
		for(k = 0, i = low; i <= high; i++, k++){
			arr[i] = arr2[k];
		}
	}
	
	public static void sort(int[] arr, int l, int r){
		if(l >= r){
			return;
		}		
		int mid = (l + r)/2;
		sort(arr, l, mid);
		sort(arr, mid + 1, r);
		Merge(arr, l, mid, r);
	}
	
	public static void main(String[] args){
		int[] arr = {9, 8, 7, 13, 21, 1, 17, 6};
		System.out.println("排序前:");
		for(int i = 0; i < arr.length; i++){
			System.out.print(arr[i] + ",");
		}
		
		sort(arr, 0, arr.length-1);
		
		System.out.println("\n排序后:");
		for(int i = 0; i < arr.length; i++){
			System.out.print(arr[i] + ",");
		}
	}
}






© 著作权归作者所有

Amui
粉丝 4
博文 78
码字总数 40874
作品 0
广州
程序员
私信 提问
java泛型中使用的排序算法——归并排序及分析

一、引言 我们知道,java中泛型排序使用归并排序或TimSort。归并排序以O(NlogN)最坏时间运行,下面我们分析归并排序过程及分析证明时间复杂度;也会简述为什么java选择归并排序作为泛型的排序...

9龙
04/29
0
0
可视化的数据结构和算法

还记得之前发布过的那个关于可视化排序的文章吗?在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看。我把这个页面的目录列在下...

戴威
2011/05/12
1K
5
面试 11:玩转 Java 归并排序

面试 11:Java 玩转归并排序 前面讲了冒泡、选择、插入三种简单排序,时间复杂度都是 O(n²),今天,我们终于迎来了更高级的排序:归并排序。 虽然在这之前还有希尔排序和堆排序,但由于时间...

nanchen2251
2018/07/18
0
0
可视化的数据结构和算法

还记得之前发布过的那个关于可视化排序的文章吗?在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看。我把这个页面的目录列在下...

戴威
2011/05/12
19
0
《数据结构与算法系列》合集整理

《数据结构与算法系列》合集整理 整理来自博客园skywang12345,以下摘自作者介绍: “最近抽空整理了"数据结构和算法"的相关文章。在整理过程中,对于每种数据结构和算法分别给出"C"、"C++"...

kaixin_code
2018/12/01
178
0

没有更多内容

加载失败,请刷新页面

加载更多

Qt程序打包发布方法(使用官方提供的windeployqt工具)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/toTheUnknown/article/details/81748179 如果使用到了Qt ...

shzwork
28分钟前
4
0
MainThreadSupport

MainThreadSupport EventBus 3.0 中的代码片段. org.greenrobot.eventbus.MainThreadSupport 定义一个接口,并给出默认实现类. 调用者可以在EventBus的构建者中替换该实现. public interface ...

马湖村第九后羿
49分钟前
3
0
指定要使用的形状来代替文字的显示

控制手机键盘弹出的功能只能在ios上实现,安卓是实现不了的,所以安卓只能使用type类型来控制键盘类型,例如你要弹出数字键盘就使用type="number",如果要弹出电话键盘就使用type="tel",但这...

前端老手
59分钟前
6
0
总结:Raft协议

一、Raft协议是什么? 分布式一致性算法。即解决分布式系统中各个副本数据一致性问题。 二、Raft的日志广播过程 发送日志到所有Followers(Raft中将非Leader节点称为Follower)。 Followers收...

浮躁的码农
今天
7
0
Flask-admin Model View字段介绍

Model View字段介绍 can_create = True 是否可以创建can_edit = True 是否可以编辑can_delete = True 是否可以删除list_template = 'admin/model/list.html' 修改显......

dillonxiao
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部