文档章节

排序算法笔记:快速排序 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
08《Java核心技术》之Vector、ArrayList、LinkedList有何区别?

一、提出问题 我们在日常的工作中,能够高效地管理和操作数据是非常重要的。由于每个编程语言支持的数据结构不尽相同,比如我们最早接触到的 C 语言,需要自己实现很多基础数据结构,管理和操...

飞鱼说编程
10/11
0
0
算法和编程面试题精选TOP50!(附代码+解题思路+答案)

作者 | javinpaul 编译 | 王天宇、Jane 整理 | Jane 出品 | AI科技大本营 【导读】之前我们给同学们推荐了很多关于 Python 的面试资源,大家都表示很有用。这次营长表示要翻 Java 的牌子啦~...

AI科技大本营
09/27
0
0
算法和编程面试题精选 TOP50!(附代码+解题思路+答案)

作者 | javinpaul 出品 | AI科技大本营 数组 数组,将元素存储到内存的连续位置中,是最基本的数据结构。在任何和编程相关的面试中,都会被问到和数组相关的问题,可以说是非常热门的考题之一...

CSDN资讯
10/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

IDEA中Maven打包时如何跳过测试

方法1:直接使用IDEA提供的方式 Maven命令栏的工具栏有下图中的图标,上面就写着 Skip Tests 按下图标后,如下图,test就不可用了 直接使用package命令即可。 方法2:自己编辑maven命令 进入...

karma123
18分钟前
2
0
Device eth0 does not seem to be present,delaying initialization.

场景:在进行linux 主机克隆的时候,网卡初始化一般都会有问题,最常见的“Device eth0 does not seem to be present,delaying initialization.”,从字面意思 说eth0没有固化,延迟启动。由...

hnairdb
18分钟前
1
0
国内首个区块链试验区在海南成立

据新华社报道,10月8日,海南自贸区(港)区块链试验区正式在海南生态软件园授牌设立,这也是目前为止国内第一个区块链试验区。 该试验区位于海南生态软件园,与试验区同一天成立还有2家研究...

linuxCool
30分钟前
1
0
Java日期和时间获取问题

获取年月日时分秒 Calendar cal = Calendar.getInstance();//获取年int year = cal.get(Calendar.YEAR);//获取月,范围是0-11,最后使用需+1int month = cal.get(Cal...

lanyu96
49分钟前
11
0
Ceph学习笔记2-在Kolla-Ansible中使用Ceph后端存储

环境说明 使用Kolla-Ansible请参考《使用Kolla-Ansible在CentOS 7单节点上部署OpenStack Pike》; 部署Ceph服务请参考《Ceph学习笔记1-Mimic版本多节点部署》。 配置Ceph 以osdev用户登录: ...

LastRitter
53分钟前
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部