文档章节

Java四种数组排序

fog.
 fog.
发布于 2012/07/24 16:26
字数 842
阅读 163
收藏 8
package algorithm.sort;

import java.util.Random;

/**
 * @author  szy 
 * 2012-7-24
 */
public class Sort {
	/**
	 * 选择排序法
	 * 
	 * 基本思路:将要排序的数组分成两部分, 
	 * 一部分是从小到大已经排好序的,一部分是无序的, 
	 * 从无序的部队取出最小的数值,放到已经排好序的部分的最后
	 * 
	 * @param arr
	 * @return 
	 */
	public int[] choiceSort(int[] arr){
		int t,i=0,j;
		int len = arr.length;
		for(;i<len;i++){
			int m = i;
			for(j=i+1;j<len;j++){
				//如果j元素比m元素小,将j赋值给m
				if(arr[j] < arr[m]){
					m=j;
				}
			}
			//交换m和i两个元素的位置
			if(i != m){
				t = arr[i];
				arr[i] = arr[m];
				arr[m]=t;
			}
		}
		return arr;
	}
	
	/**
	 * 冒泡排序
	 * 
	 * 基本思路:从数组开始扫描待排序的元素
	 * 在扫描过程中依次对相邻元素进行比较,将数值大的元素后移
	 * 每经过一趟排序后,数值最大的元素将移到末尾
	 * 此时记下该元素的位置,
	 * 下一趟排序只需要比较到些位置为止
	 * 直到所有元素都己有序排列
	 * @param arr
	 * @return 
	 */
	public int[] bubblingSort(int[] arr){
		int t,i=0,j=0;
		int len = arr.length;
		for(;i<len;i++){
			//循环比较相邻两个元素大小
			for(;j<len-i-1;j++){
				//比较相邻元素大小,小的前移,大的后移
				if(arr[j]>arr[j+1]){
					t=arr[j];
					arr[j]=arr[j+1];
					arr[j+1]=t;
				}
			}
		}
		return arr;
	}
	
	/**
	 * 插入排序
	 * 
	 * 基本思路:将要排序的数组分成两部分
	 * 每次从后面的数组部分中取出索引最小的数组元素
	 * 插入到前面数组部分的适当位置中.
	 * 通常在开始排序时,将数组的第一个元素为一组,后面的所有元素被当成另一组
	 * 
	 * @param arr
	 * @return 
	 */
	public int[] insertSort(int[] arr){
		//将第一个元素看做一部分,第二个元素看做另一部分
		//从第二部分中依次取元素插入到第一部分中
		int i=1,j;
		int len = arr.length;
		for(;i<len;i++){
			int tmp = arr[i];
			j = i-1;
			//依次和i前面元素比较,寻找合插入位置
			while(tmp < arr[j]){
				arr[j+1] = arr[j];
				j--;
				if(j == -1){
					break;
				}
			}
			//将插入元素插入到合适位置
			arr[j+1] = tmp;
		}
		return arr;
	}
	
	/**
	 * 快速排序
	 * 
	 * 基本思路:将一个大的数组的排序分题,分解成2个小的数组的排序
	 * 而每个小的数组排序又可以继续分解成更小的2个数组.
	 * 这样一直递归分解下去 ,直到数组的大小最大为2
	 * 
	 * @param arr
	 * @param right arr.length-1
	 * @param left  0  
	 * @return 
	 */
	public int[] quickSort(int[] arr, int left, int right){
		int t,len = arr.length;
		
		if(left < right){
			int s = arr[left];
			int i = left;
			int j = right + 1;
			while(true){
				//向右找大于s的数的索引 
				while(i+1 < len && arr[++i] < s );
				//向左找小于s的数的索引
				while(j-1 > -1 && arr[--j] > s);
				//如果 i>=j 退出循环
				if(i>=j)
					break;
				else{
					//交换i和j位置
					t = arr[i];
					arr[i] = arr[j];
					arr[j] = t;
				}
			}
			arr[left] = arr[j];
			arr[j] = s;
			//对左边进行递归
			quickSort(arr,left,j-1);
			//对右边进行递归
			quickSort(arr,j+1,right);
		}
		return arr;
	}
	
	// Test
	public static void main(String[] args) {
		int i = 0, len = 100000;
		int[] arr = new int[len];
		Random rd = new Random();
		for (; i < len; i++) {
			arr[i] = rd.nextInt(len);
		}

		long millis = System.currentTimeMillis();
		 //new Sort().bubblingSort(arr); //26秒
		 //new Sort().choiceSort(arr); //287秒
		 new Sort().insertSort(arr);   //172秒
		//new Sort().quickSort(arr, 0, len - 1);//19秒
		for (i = 0; i < len; i++) {
			System.out.println(arr[i]);
		}

		System.out.println("用时:" + (System.currentTimeMillis() - millis) / 100
				+ "秒");
	}
}

© 著作权归作者所有

共有 人打赏支持
fog.
粉丝 10
博文 32
码字总数 11708
作品 0
深圳
程序员
私信 提问
加载中

评论(2)

迷之老王
迷之老王

引用来自“jellyzi”的评论

手机端看会代码溢出

wp7毫无压力的说。
jellyzi
jellyzi
手机端看会代码溢出
JAVA中运用数组的四种排序方法

JAVA中在运用数组进行排序功能时,一般有四种方法:快速排序法、冒泡法、选择排序法、插入排序法。 快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。 冒泡法是运用遍历数组进...

IceRainYWC
2014/03/17
0
0
JAVA中运用数组的四种排序方法

JAVA中在运用数组进行排序功能时,一般有四种方法:快速排序法、冒泡法、选择排序法、插入排序法。 快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。 冒泡法是运用遍历数组进...

闫三
2012/05/08
0
0
Scala学习(三)数组相关操作

1.定长数组 如果你需要一个长度不变的始祖,可以使用Scala中的Array。例如: 2.变长数组:数组缓冲 对于那种长度有变化的数组,Java有ArrayList,C++有vector。Scala中有等效的数据结构Array...

我爱春天的毛毛雨
09/30
0
0
Learn Java - Chapter 1 变量(Variables)-数组(Arrays)

Java数组在被创建的时候确定数组长度。索引下标从0开始。 1.数组定义及初始化 int[] anArray;//定义anArray = new int[2];//初始化anArray[0] = 100;//赋值anArray[1] = 200;//赋值 System.o...

Hassan
2015/06/01
0
0
可视化的数据结构和算法

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

戴威
2011/05/12
962
5

没有更多内容

加载失败,请刷新页面

加载更多

中国龙-扬科
26分钟前
2
0
使用vuex的state状态对象的5种方式

vuex是一个专门为vue.js设计的状态管理模式,并且也可以使用devtools进行调试。 下面给大家来贴一下我的vuex的结构 下面是store文件夹下的state.js和index.js内容 //state.jsconst state =...

peakedness丶
30分钟前
2
0
NetCore MVC Demo

地址:http://114.116.9.72:5411

whltian
37分钟前
1
0
Netty handle方法周期 (四)

写了一个练习之后,发现自定义的助手类每次肯定是必须的,对于不同的业务逻辑需求,会写相对应的逻辑 最简单的查看Handle生命周期的方式,就是重写上级方法,看名字差不多应该可以知道方法的作用 ...

_大侠__
42分钟前
9
0
vue主动刷新页面及列表数据删除后的刷新实例

1.场景 在处理列表时,常常有删除一条数据或者新增数据之后需要重新刷新当前页面的需求。 2.遇到的问题 1. 用vue-router重新路由到当前页面,页面是不进行刷新的 2.采用window.reload(),或者...

前端小攻略
53分钟前
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部