文档章节

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.
粉丝 11
博文 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
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
阿里历年经典Java面试题汇总

Volatile的特征: A、禁止指令重排(有例外) B、可见性 Volatile的内存语义: 当写一个volatile变量时,JMM会把线程对应的本地内存中的共享变量值刷新到主内存。 当读一个volatile变量时,J...

Java团长17
07/11
0
0
java 通配符的应用— java 排序算法

这几天无聊,又重新学起java的排序算法,为DualPivotQuickSort做准备。为了更好地适应各种情况,我们选择使用通用类型T和通配符的上下界来实现,同时这次谈的是对数组对象的排序。如果你对j...

天地一MADAO_
2014/03/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSX | SafariBookmarksSyncAgent意外退出解决方法

1. 启动系统, 按住⌘-R不松手2. 在实用工具(Utilities)下打开终端,输入csrutil disable, 然后回车; 你就看到提示系统完整性保护(SIP: System Integrity Protection)已禁用3. 输入reboot回车...

云迹
今天
4
0
面向对象类之间的关系

面向对象类之间的关系:is-a、has-a、use-a is-a关系也叫继承或泛化,比如大雁和鸟类之间的关系就是继承。 has-a关系称为关联关系,例如企鹅在气候寒冷的地方生活,“企鹅”和“气候”就是关...

gackey
今天
4
0
读书(附电子书)|小狗钱钱之白色的拉布拉多

关注公众号,在公众号中回复“小狗钱钱”可免费获得电子书。 一、背景 之前写了一篇文章 《小狗钱钱》 理财小白应该读的一本书,那时候我才看那本书,现在看了一大半了,发现这本书确实不错,...

tiankonguse
今天
4
0
Permissions 0777 for ‘***’ are too open

异常显示: @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ WARNING: UNPROTECTED PRIVATE KEY FILE! @ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ ......

李玉长
今天
5
0
区块链10年了,还未落地,它失败了吗?

导读 几乎每个人,甚至是对通证持怀疑态度的人,都对区块链的技术有积极的看法,因为它有可能改变世界。然而,区块链技术问世已经10年了,我们仍然没有真正的用上区块链技术。 几乎每个人,甚...

问题终结者
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部