文档章节

Java四种数组排序

fog.
 fog.
发布于 2012/07/24 16:26
字数 842
阅读 163
收藏 8
点赞 0
评论 2
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
手机端看会代码溢出
Scala笔记整理(二):Scala数据结构—数组、map与tuple

[TOC] 数组 定长数组 如果你需要一个长度不变的数组,可以用Scala中的Array。例如: 在JVM中,Scala的Array以Java数组方式实现。示例中的数组在JVM中的类型为java.lang.String[]。Int、Doubl...

xpleaf ⋅ 04/18 ⋅ 0

你所需要的java提升篇大总结

java基础篇深入解析大总结 java基础(一) 深入解析基本类型 java基础(二) 自增自减与贪心规则 java基础(三) 加强型for循环与Iterator java基础(四) java运算顺序的深入解析 java基础(五) Str...

sihailoveyan ⋅ 04/25 ⋅ 0

Java编程学习之泛型方法的了解 java开发

Java泛型方法和泛型类支持程序员使用一个方法指定一组相关方法,或者使用一个类指定一组相关的类型。 Java泛型是JDK 5中引入的一个新特性,泛型提供了编译时类型安全检测机制,该机制允许程序...

老男孩Linux培训 ⋅ 05/29 ⋅ 0

全面的java编程新手入门学习笔记总结

Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和安全性,广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互...

Java小辰 ⋅ 05/10 ⋅ 0

java编程语言学习:异常处理

Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和安全性,广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互...

Java小辰 ⋅ 06/01 ⋅ 0

JNI开发流程与引用数据类型的处理

今天我们来看下Java JNI,先看下维基百科给的定义, JNI, Java Native Interface, Java本地接口,是一种编程框架,使得Java虚拟机中的Java程序可以调用本地应用或库,也可以被其他程序调用。...

juexingzhe ⋅ 05/04 ⋅ 0

一文掌握关于Java数据结构所有知识点(欢迎一起完善)

在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系...

snailclimb ⋅ 05/08 ⋅ 0

升级到JDK9的一个BUG,你了解吗

概述 前几天在一个群里看到一个朋友发了一个demo,说是JDK的bug,昨天在JVM的一个群里又有朋友发了,觉得挺有意思,分享给大家,希望大家升级JDK的版本的时候注意下是否存在这样的代码,如果...

你假笨 ⋅ 06/06 ⋅ 0

OpenJ9 和 HotSpot 的对比 Part 1

OpenJ9 和 IBM J9 是来自默认 Oracle HotSpot JVM 的不同 JVM 实现。使用现代的 adoptopenjdk 预置 Docker 镜像,你可以轻易地切换和测试不同的组合,并且可以为你选择合适的 JVM。 这个传言...

oschina ⋅ 05/28 ⋅ 0

foreach循环由于传统的for循环(46)

1、java语言支持四种类型: (1)接口(interface): (2)类(class): (3)数组(Array): (4)基本类型(primitive):唯一非引用类型(reference type) 2、方法签名:包括方法名称...

职业搬砖20年 ⋅ 05/16 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

tcp/ip详解-链路层

简介 设计链路层的目的: 为IP模块发送和接收IP数据报 为ARP模块发送ARP请求和接收ARP应答 为RARP模块发送RARP请求和接收RARP应答 TCP/IP支持多种链路层协议,如以太网、令牌环往、FDDI、RS-...

loda0128 ⋅ 今天 ⋅ 0

spring.net aop代码例子

https://www.cnblogs.com/haogj/archive/2011/10/12/2207916.html

whoisliang ⋅ 今天 ⋅ 0

发送短信如何限制1小时内最多发送11条短信

发送短信如何限制1小时内最多发送11条短信 场景: 发送短信属于付费业务,有时为了防止短信攻击,需要限制发送短信的频率,例如在1个小时之内最多发送11条短信. 如何实现呢? 思路有两个 截至到当...

黄威 ⋅ 昨天 ⋅ 0

mysql5.7系列修改root默认密码

操作系统为centos7 64 1、修改 /etc/my.cnf,在 [mysqld] 小节下添加一行:skip-grant-tables=1 这一行配置让 mysqld 启动时不对密码进行验证 2、重启 mysqld 服务:systemctl restart mysql...

sskill ⋅ 昨天 ⋅ 0

Intellij IDEA神器常用技巧六-Debug详解

在调试代码的时候,你的项目得debug模式启动,也就是点那个绿色的甲虫启动服务器,然后,就可以在代码里面断点调试啦。下面不要在意,这个快捷键具体是啥,因为,这个keymap是可以自己配置的...

Mkeeper ⋅ 昨天 ⋅ 0

zip压缩工具、tar打包、打包并压缩

zip 支持压缩目录 1.在/tmp/目录下创建目录(study_zip)及文件 root@yolks1 study_zip]# !treetree 11└── 2 └── 3 └── test_zip.txt2 directories, 1 file 2.yum...

蛋黄Yolks ⋅ 昨天 ⋅ 0

聊聊HystrixThreadPool

序 本文主要研究一下HystrixThreadPool HystrixThreadPool hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java /** * ThreadPool used to executed {@link Hys......

go4it ⋅ 昨天 ⋅ 0

容器之上传镜像到Docker hub

Docker hub在国内可以访问,首先要创建一个账号,这个后面会用到,我是用126邮箱注册的。 1. docker login List-1 Username不能使用你注册的邮箱,要用使用注册时用的username;要输入密码 ...

汉斯-冯-拉特 ⋅ 昨天 ⋅ 0

SpringBoot简单使用ehcache

1,SpringBoot版本 2.0.3.RELEASE ①,pom.xml <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.0.3.RELE......

暗中观察 ⋅ 昨天 ⋅ 0

Spring源码解析(八)——实例创建(下)

前言 来到实例创建的最后一节,前面已经将一个实例通过不同方式(工厂方法、构造器注入、默认构造器)给创建出来了,下面我们要对创建出来的实例进行一些“加工”处理。 源码解读 回顾下之前...

MarvelCode ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部