文档章节

常用的简单排序算法集合(更新中)

维特的烦恼
 维特的烦恼
发布于 2014/04/26 21:06
字数 632
阅读 140
收藏 22
        /**
	 * 冒泡排序
	 */
	public static void Bubble_Sort(int[] a) {
		for (int i = 0; i < a.length - 1; i++) {
			for (int j = 0; j < a.length - i - 1; j++) {
				if (a[j] > a[j + 1]) {
					a[i] = a[i] + a[j];
					a[j] = a[i] - a[j];
					a[i] = a[i] - a[j];
				}
			}
		}
	}

	/**
	 * 选择排序
	 */
	public static void Select_Sort(int[] a) {
		int minIndex = 0;
		for (int i = 0; i < a.length - 1; i++) {
			minIndex = i;
			for (int j = i + 1; j < a.length; j++) {
				if (a[j] < a[minIndex]) {
					minIndex = j;
				}
			}
			if (minIndex != i) {
				a[i] ^= a[minIndex];
				a[minIndex] ^= a[i];
				a[i] ^= a[minIndex];
			}
		}
	}

	// 插入排序
	public static void Insert_Sort(int[] a) {
		int length = a.length;
		int insertval = 0;
		int index = 0;
		for (int i = 1; i < length; i++) {
			insertval = a[i];
			index = i - 1;
			/**
			 * 5 4 3 2 1
			 * 4 5 3 2 1
			 * 3 4 5 2 1
			 * 2 3 4 5 1
			 * 1 2 3 4 5
			 */
			while (index >= 0 && insertval < a[index]) {
				a[index + 1] = a[index];
				index--;
			}

			a[index + 1] = insertval;
		}

	}

	/**
	 * 快速排序——双向检索,返回调整后key的位置
	 */
	private static void part(int l, int r, int A[]) {

		if (l < r) {
			int i = l, j = r;
			int key = A[i];// 取出收个数作为key,挖出第一个坑
			while (i < j) {
				// 循环从末尾找到第一个比key小或等于的数的索引j
				while (i < j && A[j] > key)
					j--;

				if (i < j)
					// 将这个比key小的数填入key处的坑,形成新坑索引j,同时增加索引i
					A[i++] = A[j];
				// 循环从i开始找到第一个打大于key的数字索引i
				while (i < j && A[i] < key)
					i++;

				if (i < j)
					// 将这个数填入上次的坑j内,同时j向下更新
					A[j--] = A[i];
			}
			// 将key值填入中坑
			A[i] = key;
			part(l, i - 1, A);
			part(i + 1, r, A);
		}
	}

	/**
	 * 快速排序——单向搜索 由小到大
	 */
	private static void part_single_s2b(int l, int r, int[] A) {

		if (l < r) {
			int i = l - 1;
			int key = A[r];
			for (int j = l; j < r; j++) {
				if (A[j] > key) {
					i++;
					int tmp = A[i];
					A[i] = A[j];
					A[j] = tmp;
				}
			}
			A[r] = A[i + 1];
			A[i + 1] = key;
			part_single_s2b(l, i, A);
			part_single_s2b(i + 2, r, A);
		}

	}

关于快排序单扫描的解释:图摘自结构之法大神博客:http://blog.csdn.net/v_JULY_v/article/details/6262915

关于挖坑填数的双向扫描:
参加此大神博客:http://www.cnblogs.com/morewindows/archive/2011/08/13/2137415.html

Console:

=======随机数组100000个数据=======
=======耗时0.014毫秒=======
=======快速排序,双向扫描快速排序,生成有序数列=======
=======耗时0.016毫秒=======
=======快速排序,单向扫描快速排序,由大到小=======
=======耗时0.232毫秒=======
=======快速排序,双向扫描快速排序,由小到大=======
=======耗时0.005毫秒=======
=======冒泡排序,由小到大=======
=======耗时2.541毫秒=======
=======选择排序,由小到大=======
=======耗时3.741毫秒=======
=======插入排序,由小到大=======
=======耗时0.004毫秒=======


© 著作权归作者所有

维特的烦恼
粉丝 20
博文 97
码字总数 42329
作品 0
天津
私信 提问
加载中

评论(1)

徐贺年
徐贺年
实用
涨姿势,图文带你了解 8 大排序算法

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 常见的内部排序算法有...

Java架构
2018/07/25
0
0
Java 中的 Collection 学习笔记(1)

Collection 来自与java.util包,是java中数据结构的封装的包。 collection主要方法: boolean add(Object o)添加对象到集合 boolean remove(Object o)删除指定的对象 int size()返回当前集合中...

hellation_
03/29
0
0
面试中常用排序算法实现(Java)

当我们进行数据处理的时候,往往需要对数据进行查找操作,一个有序的数据集往往能够在高效的查找算法下快速得到结果。所以排序的效率就会显的十分重要,本篇我们将着重的介绍几个常见的排序算...

Single_YAM
2017/10/30
0
0
线程基础:多任务处理(13)——Fork/Join框架(解决排序问题)

============== 接上文《 线程基础:多任务处理(12)——Fork/Join框架(基本使用)》 3. 使用Fork/Join解决实际问题 之前文章讲解Fork/Join框架的基本使用时,所举的的例子是使用Fork/Join...

yinwenjie
2017/05/14
0
0
面试 13:基于排序算法的总结

浑浑噩噩,我们前面已经讲解了冒泡、插入、选择、归并、快排 5 种排序算法,其他的由于时间关系,我们就不一一例举了。 说到排序,不得不想到我们 JDK 中自带的 和 方法。这两个方法基本算是...

nanchen2251
2018/07/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

一次看懂 Https 证书认证

TLS > 传输层安全性协定 TLS(Transport Layer Security),及其前身安全套接层 SSL(Secure Sockets Layer)是一种安全协议,目的是为网际网路通信,提供安全及数据完整性保障。 如图,TLS...

极客收藏夹
35分钟前
4
0
https证书买哪家好?有哪些供应商

在选购https证书前除了要了解类型外,还需要了解https证书供应商,毕竟不同的供应商,提供的产品质量与服务也是有差异的。今天小编就为大家讲讲https证书供应商方面的内容,希望各位会喜欢。...

安信证书
36分钟前
5
0
Zuul 配置

概述:zuul底层是基于servlet,是由一系列的filter链构成。 1、路由配置 a、单例serverId映射 zuul: routes: client-a: path: /client/** serviceId: client-a 意思是...

java框架开发者
54分钟前
3
0
zk中FinalRequestProcessor解析

是处理器最后一个环节 FinalRequestProcessor implements RequestProcessor 处理器链最后一个环节处理事务和非事务请求最后一个环节 构造器 public FinalRequestProcessor(ZooKeeperServer z...

writeademo
54分钟前
3
0
Axios 详解

首先祝广大程序猿们节日快乐! 一、axios简介 基于promise,用于浏览器和node.js的http客户端 二、特点 支持浏览器和 node.js 支持 promise 能拦截请求和响应 能转换请求和响应数据 能取消请求...

张兴华ZHero
55分钟前
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部