文档章节

快速排序

JiaChang
 JiaChang
发布于 2016/08/12 15:57
字数 775
阅读 5
收藏 0
点赞 0
评论 0

快速排序

基本思路:从待排序的数据序列中任取一个数据(通常是第一个数据)作为分界值,所有比分界值小的元素一律放在分界值的左边,所有比分界值大的数据一律放在分界值的右边。经过这样一趟排序下来,待排序序列被分成左,右两个子序列,左边序列中的数据都比分界值小,右边序列中的数据都比分界值大。

接下来对左,右两个子序列进行递归,对两个子序列重新选择分界值并依次规则调整,直到每个子序列的元素只剩下一个,排序完成。

具体步骤

(1)选出指定的分界值(如第一个元素)

(2)定义一个 i 变量,i 变量从左边第一个索引开始,找大于分界值的元素的索引,并用 i 来记录它。

(3)定义一个 j 变量,j 变量从右边第一个索引开始,找小于分界值的元素的索引,并用 j 来记录它。

(4)如果 i < j ,则交换 i , j两个索引处的元素。

重复执行以上 2 ~ 4步,直到 i ≥ j,此时,j 左边的数据元素都小于分界值,j 右边的数据元素都大于分界值,最后将分界值和 j 索引处的元素交换即可。

因为经过一趟排序之后,分界值的位置在待排序的数据元素中的位置就已经确定下来了,所以继续分别递归分界值左边的子序列和右边的子序列,直至每个子序列的元素只剩一个,排序结束。

快速排序的实现:

	/***
	 * 对data数组中从start到end索引范围内的子虚列进行排序
	 * 使之满足所有小于分界值的放在左边,所有大于分界值的放在右边
	 * @param data 待排序数组
	 * @param start 开始下标
	 * @param end 结束下标
	 */
	public static <E> void quickSort(int[] data,int start,int end){
		//需要排序
		if(start<end){
			//以第一个元素作为分界值
			int pivot = data[start];
			// i 从左边进行搜索,搜索大于分界值的元素的索引
			int i = start;
			// j 从右边进行搜索,搜索小于分界值的元素的索引
			int j = end+1;
			while(true){
				//找到第一个大于分界值的元素的索引,或者 i 已经到end处
				while(i < end && data[++i] <= pivot);
				//找到第一个小于分界值的元素的索引,或者 j 已经到start处
				while(j > start && data[--j] >= pivot);
				//需要交换
				if(i<j){
					//交换 i j 元素
					int temp = data[i];
					data[i] = data[j];
					data[j] = temp;
				}
				//不需要交换则结束循环
				else break;
			}
			//交换 j 和 start 处的元素, 此时 j 的在排序中位置已经固定
			int temp = data[start];
			data[start] = data[j];
			data[j] = temp;
			//交换完之后,接着递归 j 的左边子序列
			quickSort(data,start,j-1);
			//递归 j 的右边的子序列
			quickSort(data,j+1,end);
		}
	} 


测试代码: 

 

 

© 著作权归作者所有

共有 人打赏支持
JiaChang
粉丝 2
博文 32
码字总数 18002
作品 0
海口
程序员

暂无相关文章

线程池

一、线程池:提供了一个线程队列,队列中保存着所有等待状态的线程。避免了创建与销毁额外开销,提高了响应的速度。 二、线程池的体系结构: java.util.concurrent.Executor : 负责线程的使用...

stars永恒 ⋅ 28分钟前 ⋅ 0

你值5K还是15K?实战案例,测测你的分析功力

本文源自陈老师遇到的真实案例。 老板说:“我们今年准备参加展会,做一年。以前我没参加过,没关系,这里有一份展会数据,你回去分析下哪些有价值,后边组织的时候有个指导”。现在你收到任...

加米谷大数据 ⋅ 29分钟前 ⋅ 0

中文转英文功能

package com.sysware.task.util;import net.sourceforge.pinyin4j.PinyinHelper;import net.sourceforge.pinyin4j.format.HanyuPinyinCaseType;import net.sourceforge.pinyin4j.for......

AK灬 ⋅ 30分钟前 ⋅ 0

JNI Java层类关联C/C++层的类

Android开发时,因为要实现某某功能,需要集成算法公司的算法库(so库),这就需要自己编写JNI。 通常这些库提供的接口可以概况成1、初始化 2、算法处理 3、释放 4、打印版本号 初始化后会返...

国仔饼 ⋅ 34分钟前 ⋅ 0

maven下载jar包改为阿里云的maven库

一:修改maven安装路径中conf文件夹下的setting.xml文件 <mirrors> <mirror> <id>alimaven</id> <name>aliyun maven</name> <url>http://maven.aliyun.com/nexus/content/......

夜醒者 ⋅ 34分钟前 ⋅ 0

电商用户行为分析大数据平台相关系列10-基础数据结构分析

电商用户行为分析大数据平台相关系列1-环境介绍 电商用户行为分析大数据平台相关系列2-HADOOP环境搭建 电商用户行为分析大数据平台相关系列3-HIVE安装 电商用户行为分析大数据平台相关系列4...

xiaomin0322 ⋅ 35分钟前 ⋅ 0

使用readLine()方法遇到的坑

下午玩 TCP/IP 的 Socket 通信时,使用 BufferedReader 的 readLine() 遇到了一个坑,现在终于解决了,特此记录下来。 程序很简单,客户段从控制台读取用户输入,然后发送至服务器端,主要代...

孟飞阳 ⋅ 35分钟前 ⋅ 0

基于Hadoop集群的Hive安装配置(Derby数据库)

Hive是一个数据仓库基础工具在Hadoop中用来处理结构化数据,提供简单的sql查询功能,可以将sql语句转换为MapReduce任务进行运行(具体的Hive架构大家自行搜索)。接下来主要讲下Hadoop集群下...

海岸线的曙光 ⋅ 36分钟前 ⋅ 0

CoreOS裸机iso安装和相关配置

裸机通过iso安装CoreOS,个人趟了很多坑,以下就是完整的从零开始部署和配置的过程,希望对大家有用。 一、安装CoreOS到硬盘 1. 准备Live iso镜像,制作好usb启动盘 Live iso下载地址 2. 搭建...

ykbj ⋅ 41分钟前 ⋅ 0

jquery控制表格锁列(转)

表格已经完成后新加的需求,要实现锁表格的第一列。很多带这种效果的都是js封装的框架或者具体某种框架的组件,不适用解决当前问题。作为后端开发又实在不熟样式,搜到了一个可以用的,虽然样...

刘昌鑫 ⋅ 43分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部