文档章节

快速排序

JiaChang
 JiaChang
发布于 2016/08/12 15:57
字数 775
阅读 5
收藏 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
海口
程序员

暂无文章

八大包装类型的equals方法

先看其中一个源码 结论:八大包装类型的equals方法都是先判断类型是否相同,不相同则是false,相同则判断值是否相等 注意:包装类型不能直接用==来等值比较,否则编译报错,但是数值的基本类型...

xuklc
39分钟前
1
0
NoSQL , Memcached介绍

什么是NoSQL 非关系型数据库就是NoSQL,关系型数据库代表MySQL 对于关系型数据库来说,是需要把数据存储到库、表、行、字段里,查询的时候根据条件一行一行地去匹配,当量非常大的时候就很耗...

TaoXu
昨天
0
0
890. Find and Replace Pattern - LeetCode

Question 890. Find and Replace Pattern Solution 题目大意:从字符串数组中找到类型匹配的如xyy,xxx 思路: 举例:words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"abc ......

yysue
昨天
0
0
Linux | Redis

写在前面的话 常言道,不作笔记不读书。在下是深有体会啊,所以,跟我一起做下本节的笔记吧,或许多年以后,你一定会感谢今天的你。 安装 在官网的下载页 Redis Download 直接写了在Linux的安...

冯文议
昨天
1
0
NoSQL-memcached

NoSQL介绍 NoSQL叫非关系型数据库。而关系型数据库代表有MySQL。对于关系型数据库来说,是需要把数据存储到库、表、行、字段里,查询的时候根据条件一行一行地去匹配,当量非常大的时候就很...

ln97
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部