文档章节

快速排序

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
海口
程序员
私信 提问

暂无文章

eslint rules 规则

'rules': { "comma-dangle": ["error", "never"], //是否允许对象中出现结尾逗号 "no-cond-assign": 2, //条件语句的条件中不允许出现赋值运算符 "no-console": 2, //不允许出现console语句 ...

agenyun
15分钟前
0
0
类型判断时instanceof和equals的不同用法

接口设计时为了避免序列化的麻烦,将接口定义为参数为map<String,String>类型的接口,但是现在调用时需要转换当前的实体Bean为Map,接口接收方再把Map转换为另一个Bean实体。过程中的需要对类...

wangtx
21分钟前
0
0
vue 组件间传值(个人精编)

1.父组件向子组件传值 1⃣️.子组件标签绑定需要传递的参数名2⃣️.子组件页面使用props 接收参数 2.子组件向父组件传值  1⃣️.子组件使用$emit来触发一个自定义事件,并传递一个参...

MrBoyce
31分钟前
1
0
(荷兰)彼得·冯·门施著:博物馆学研究的目的

博物馆学研究的目的 (荷)彼得·冯·门施 尽管诸多关于博物馆学认知目的的不同看法可以被归纳为数个主要群体,但没有一个群体可以被称为“学派”。一般来说,学派是由于博物馆学研究目的的不...

乔老哥
41分钟前
2
0
Vue slot的用法

之前看官方文档,由于自己理解的偏差,不知道slot是干嘛的,看到小标题,使用Slot分发内容,就以为 是要往下派发内容。然后就没有理解插槽的概念。其实说白了,使用slot就是先圈一块地,将来...

peakedness丶
53分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部