文档章节

快速排序详解 Java实现

小车车
 小车车
发布于 2016/09/03 10:16
字数 632
阅读 229
收藏 2

精选30+云产品,助力企业轻松上云!>>>

一、快速排序的优缺点

        对一个东西,首先要讲他的利与弊,才知道怎么使用它。快速排序适用于各种不同的输入数据且在一般应用中比其他排序都要快得多。快速排序引人注目的特点包括它是原地排序(只需要一个很小的辅助栈),且长度为N的数组排序所需的时间和NlgN成正比。它的主要缺点是非常脆弱,在实现时要非常小心才能避免低劣的性能。

        有了对比,才能知道它的好处。其实快速排序是一种分治的排序算法。它将一个数组分成两个子数组,将两部分独立地排序。讲到这里,有人就会有个疑问,那不是和归并排序一样吗?合并排序也是分治算法的一种,也是将一个数组分成两个子数组。快速排序和归并排序时互补的:归并排序将数组分成两个子数组分别排序,并将有序的子数组归并以整个数组排序;而快速排序将数组排序的方式则是当两个数组都有序时整个数组也就自然有序了。在第一种情况下,递归调用发生在处理整个数组之前;在第二种情况下,递归调用发生在处理整个数组之后。在归并排序中,一个数组被等分为两半;在快速排序中,切分的位置取决于数组的内容。这句话最重要。

二、快速排序的实现

public class Quick{
	public static void sort(Comparable[] a){
		StdRandom.shuffle(a);//消除对输入的依赖,直接生成随机数
		
		sort(a,0,a.length-1);
		
	}
	private static void sort(Comparable[] a, int lo, int hi){
		if(hi <= lo) return;
		int j= partition(a,lo,hi);//切分
		sort(a,lo,j-1);
		sort(a,j+1,hi);
	}
	private static int partition(Comparable[] a, int lo ,int hi){
		int i = io,j=hi+1;
		Comparable v = a[lo];
		while(true){
			while(less(a[++i],v)) if(i==hi) break;
			while(less(v,a[--j])) if(j==lo) break;
			if(i>=j) break;
			exch(a,i,j)
		}
		exch(a,lo,j);
		return j;
	}
	
	private static void exch(Comparable[] a ,int i ,int j){
		Comparable t = a[i];a[i]=a[j];a[j]=t;
	}
	private static boolean less(Comparable v , Comparable w){
		return v.compareTo(w)<0;
	}
}

 

 

小车车
粉丝 6
博文 98
码字总数 115586
作品 0
深圳
程序员
私信 提问
加载中
请先登录后再评论。
《数据结构与算法系列》合集整理

《数据结构与算法系列》合集整理 整理来自博客园skywang12345,以下摘自作者介绍: “最近抽空整理了"数据结构和算法"的相关文章。在整理过程中,对于每种数据结构和算法分别给出"C"、"C++"...

kaixin_code
2018/12/01
317
0
JAVA中运用数组的四种排序方法

JAVA中在运用数组进行排序功能时,一般有四种方法:快速排序法、冒泡法、选择排序法、插入排序法。 快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。 冒泡法是运用遍历数组进...

zhengguogaun
2013/06/19
21
0
JAVA中运用数组的四种排序方法

JAVA中在运用数组进行排序功能时,一般有四种方法:快速排序法、冒泡法、选择排序法、插入排序法。 快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。 冒泡法是运用遍历数组进...

IceRainYWC
2014/03/17
56
0
Java程序员进化为架构师需要掌握的知识

Java程序员进化为架构师掌握的知识: 一:Java知识 1、进制转换 2、Java基本数据类型 面向对象相关知识 3、类、接口、抽象类 this关键字、static关键字、final关键字 方法的参数传递机制 Ja...

andogo
2014/05/16
2.4K
3
JAVA中运用数组的四种排序方法

JAVA中在运用数组进行排序功能时,一般有四种方法:快速排序法、冒泡法、选择排序法、插入排序法。 快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。 冒泡法是运用遍历数组进...

闫三
2012/05/08
75
0

没有更多内容

加载失败,请刷新页面

加载更多

define()与const - define() vs. const

问题: In PHP, when do you use 在PHP中,何时使用 define('FOO', 1); and when do you use 以及何时使用 const FOO = 1; ? ? What are the main differences between those two? 两者之......

法国红酒甜
20分钟前
26
0
将Node.js升级到最新版本 - Upgrading Node.js to latest version

问题: So, I have Node.js installed and now when I tried to install Mongoosejs I got an error telling me that I don't have the needed version of Node.js (I have v0.4.11 and v0.4......

javail
今天
17
0
等到所有jQuery Ajax请求都完成了吗? - Wait until all jQuery Ajax requests are done?

问题: How do I make a function wait until all jQuery Ajax requests are done inside another function? 我如何让一个函数等到所有jQuery Ajax请求都在另一个函数中完成之后? In short...

富含淀粉
今天
17
0
OSChina 周日乱弹 —— 那么长的绳子,你这是放风筝呢

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @ 巴拉迪维:黑豹乐队的单曲《无地自容》 耳畔突然响起旋律,是那首老歌。中国摇滚有了《一无所有》不再一无所有;中国摇滚有了《无地自容》不...

小小编辑
今天
69
1
《吐血整理》-顶级程序员书单集

你知道的越多,你不知道的越多 给岁月以文明,而不是给文明以岁月 前言 王潇:格局决定了一个人的梦想,梦想反过来决定行为。 那格局是什么呢? 格局是你能够看见的深度、广度和密度。 王潇认...

敖丙
2019/12/11
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部