文档章节

排序算法笔记:快速排序 QuickSort in java

CheN_exe
 CheN_exe
发布于 2014/01/04 13:40
字数 281
阅读 262
收藏 0
/**
 * 快速排序
 * 简述:
 * 		取array[high],将之前小于array[high]的数字置于array[high]之前,大于array[high]的置于array[high]之后,最后将array[high]放置于比它大的数字和比它小的数字之间.再利用递归重复之前的步骤至low < high为止.
 * 时间复杂度:
 * 		the best case: T(n)=T(n - 1)+Θ(n) = Θ(n^2)
 * 		the worst case: T(n)<=2T(n/2)+Θ(n)=Θ(nlgn)
 * 		average case: T(n)<=T(9n/10)+T(n/10)+cn=O(nlgn)
 * 空间复杂度:
 * 		O(logn)
 * 优点:
 * 		常见通用性较高的算法中,时间复杂度非常低的算法.推荐算法.
 * 缺点:
 * 		
 * 可改进:
 * 		
 * @author CheN
 *
 */
public class QuickSort {
	public static int[] asc(int[] array) {
		quickSort(array, 0 , array.length - 1 );
		return array;
	}
	
	private static void quickSort(int[] array, int low , int high ){
		if( low < high ){
			int middle = getMiddle( array , low , high );
			quickSort( array , low , middle - 1 );
			quickSort( array , middle + 1 , high );
		}
	}
	
	private static int getMiddle(int[] array, int low , int high ){
		int x = array[high];
		for( int j = low ; j < high ; j++ ){
			if( array[j] <= x ){
				int temp = array[low];
				array[low] = array[j];
				array[j] = temp;
				low++;
			}
		}
		int temp = array[low];
		array[low] = array[high];
		array[high] = temp;
		return low;
	}
	
}


若有错误或不妥之处,敬请谅解并指点。

© 著作权归作者所有

共有 人打赏支持
CheN_exe
粉丝 2
博文 40
码字总数 17192
作品 0
海淀
程序员
私信 提问
java 通配符的应用— java 排序算法

这几天无聊,又重新学起java的排序算法,为DualPivotQuickSort做准备。为了更好地适应各种情况,我们选择使用通用类型T和通配符的上下界来实现,同时这次谈的是对数组对象的排序。如果你对j...

天地一MADAO_
2014/03/02
0
0
JDK提供的排序算法是怎么实现的?

前几天整理的一套面试题,其中有一个问题就是Java的JDK中我们见到的Collections.sort()和Arrays.sort()这两个排序算法的实现方式是什么,很多小伙伴心里边默认的应该是快排,但是不全对或者理...

HOT_POT
07/29
0
0
O(n*logn)级别的算法之二(快速排序)的三种实现方法详解及其与归并排序的对比

一,单路快排 1.测试用例: 1 #ifndef INC06QUICKSORTDEALWITHNEARLYORDEREDARRAYSORTTESTHELPERH 2 #define INC06QUICKSORTDEALWITHNEARLYORDEREDARRAYSORTTESTHELPERH 3 #include 4 #incl......

Tom-shushu
11/19
0
0
函数式思维和函数式编程

作为一个对Hashell语言[1]彻头彻尾的新手,当第一次看到一个用这种语言编写的快速排序算法的优雅例子时,我立即对这种语言发生了浓厚的兴趣。下面就是这个例子: 我很困惑。如此的简单和漂亮...

oschina
2014/09/05
11.1K
24
算法设计:两种快速排序代码实现

快速排序是一种高效且使用广泛的排序算法,在很多语言的标准库中自带的排序都是快速排序,所以我们也有必要了解快排的原理以及其实现方法。 快排的大致思想 快速排序实现的重点在于数组的拆分...

Sunrise_1018
11/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

eslint rules 规则

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

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

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

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

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

MrBoyce
今天
1
0
(荷兰)彼得·冯·门施著:博物馆学研究的目的

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

乔老哥
今天
3
0
Vue slot的用法

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

peakedness丶
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部