经典算法巡礼(六) -- 排序之快速排序

快速排序正如她的名字,她是一种排序效率相当高的算法,而且可能是应用最广泛的排序算法了。快速排序流行的原因是她实现简单,适用于各种不同的输入数据且在一般应用中比其他排序算法都要快。不仅如此,她与归并排序不同,她只需要很小的辅助空间就可以进行排序

快速排序也是分治思想的典型应用。她与归并排序是互补的:归并排序将数组分成两个子数组分别排序,并将有序的子数组归并以将整个数组排序;而快速排序而是当两个子数组都有序时,整个数组也就自己有序了。前者的递归调用发生在处理整个数组之前,而后者的递归调用发生在处理整个之后。

快速排序最主要的操作就是patition,即切分操作。选择数组中一元素,以该元素做为基准切分元素,姑且将其称为P,切分后使P之前的所有元素都小于P(排序成递增序列),P之后的所有元素都大于P。然后对P切分成的两个子数组分别再一次进行切分操作。重复此过程直到不能切分为止,即整个数组排序完成。

那么如何选择这个切分基准元素P呢?通常是随机取数组中任意值,所以快速排序的效率是和概率相关的,但实际使用过程中排序效率还是非常可观的。具体golang实现如下:

	// partition方法即为快速排序中重要的切分操作,以首元素做为基准,将剩余元素从两端寻找,分别找到大于(小于)基准的元素并交换,重复此过程直到剩余元素全部遍历为止
	func (this *QuickSort) partition(a []Comparable, compare Compare, lo int, hi int) int {
		i := lo + 1
		j := hi
		v := a[lo]
		for true {
			for this.less(a[i], v, compare) == true {
				if i == hi {
					break
				}
				i++
			}
			for this.less(a[j], v, compare) == false {
				if j == lo {
					break
				}
				j--
			}
			if i >= j {
				break
			}
			this.exch(a, i, j)
			i++
			j--
		}
		this.exch(a, lo, j)

		return j
	}

	// Sort中参数类型Comparable为统一的可比较接口,若为整数数组排序,则Comparable为int即可
	// Sort中参数类型Compare为配合Comparable接口的比较方法,若为整数数组排序,则Compare即满足a int < a int即可
	func (this *QuickSort) Sort(a []Comparable, compare Compare, lo int, hi int) {
		if hi <= lo {
			return
		}

		p := this.partition(a, compare, lo, hi)
		this.Sort(a, compare, lo, p-1)
		this.Sort(a, compare, p+1, hi)
	}

上述实现过程在切分操作时,只是简单取数组第一个元素做为切分基准元素。如此做法,排序效率则与输入序列相关了,因此可以在排序之前shuffee数组,如此一来就与概率相关了

分析快速排序的过程,可以得到每次patition时,需要N-1次比较操作(数组元素为N的情况下),同时又可得到此patition过程需要进行logN次。因此,整个快速排序需要(N-1)logN ~ NlogN次比较操作,也就是说其时间复杂度为O(NlogN)。因此,她也是可以应用于大规模数组的排序,而且也不需要归并排序大量的额外空间,同时也没有希尔排序的不确定性

当然,其实快速排序有一种方便的改进,即可在对有大量相同元素的数组排序时,效率大大提高。她是由Dijkstra提出的“三向切分的快速排序“。具体实现如下:

	// Sort方法采用”三向切分的快速排序“法进行排序
	func (this *QuickSort) Sort(a []Comparable, compare Compare, lo int, hi int) {
		if hi <= lo {
			return
		}

		lt := lo
		i := lo + 1
		gt := hi

		v := a[lo]
		for i <= gt {
			cmp := compare(v, a[i])
			if cmp < 0 {
				this.exch(a, i, gt)
				gt--
			} else if cmp > 0 {
				this.exch(a, i, lt)
				i++
				lt++
			} else {
				i++
			}
		}
		this.Sort(a, compare, lo, lt-1)
		this.Sort(a, compare, gt+1, hi)
	}

"三向切分的快速排序"中的切分方法过程如下:

她遍历数组一次,维护一个指针lt使得alo..lt-1中的元素都小于v(即切分基准元素),一个指针gt使得agt+1..hi中的元素都大于v,一个指针i使得alt..i-1全部等于v,而ai..gt中的元素都还未确定。正如上述代码中所示,等遍历完数组后,数组就分为三部分,alo..lt-1为小于v的部分,agt+1..hi为大于v的部分,而alt..gt则为等于v的部分。然后,对不等于v的部分数组再次切分递归,直到不能切分为止。

如果数组中有大量相同元素时,采用”三向切分“方法就不会对相同部分再次进行重复比较,大大提高排序性能。而当没有重复元素时,”三向切分“方法又等同时原始快速排序。因此,”三向切分的快速排序“通常被用于实际场合中进行快速排序。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏黄Java的地盘

正则表达式之进阶篇

本文主要通过介绍正则表达式中的一些进阶内容,让读者了解正则表达式在日常使用中用到的比较少但是又比较重要的一部分内容,从而让大家对正则表达式有一个更加深刻的认识。

1483
来自专栏Python爬虫实战

Python数据类型之字典(上)

之前系列文章介绍了Python简单数据类型和序列数据类型,本文来学习一种新的映射数据类型:字典。

881
来自专栏锦小年的博客

python学习笔记4.2-python高级之迭代器

迭代是Python中最强有力的特性之一,同时对编程人员来说,也是最难理解的一种用法。其实从高层次来看,迭代就是一种处理序列中元素的方式。通过自定义迭代对象可以...

21010
来自专栏nummy

python operator模块学习

operator模块是python中内置的操作符函数接口,它定义了一些算术和比较内置操作的函数。operator模块是用c实现的,所以执行速度比python代码...

752
来自专栏Modeng的专栏

Javascript数组系列五之增删改和强大的 splice()

今天是我们介绍数组系列文章的第五篇,也是我们数组系列的最后一篇文章,只是数据系列的结束,所以大家不用担心,我们会持续的更新干货文章。

1332
来自专栏星汉技术

Java API:Object class

1467
来自专栏pangguoming

理解闭包 js回收机制

为什么要有回收机制?why? 打个比方,我有一个内存卡,这个内存是8G的,我把文件,视频,音乐,都保存到了这个内存卡,随着我的储存的内容越来越多,这个内存卡已经...

4017
来自专栏CDA数据分析师

陷阱!python参数默认值

在stackoverflow上看到这样一个程序: class demo_list: def __init__(self, l=[]): ...

2138
来自专栏思考的代码世界

Python编程从入门到实践之列表|第1天

列表由一系列按特定顺序排列的元素组成。可以创建包含字母表中所有字母、数字0~9或 所有家庭成员姓名的列表;也可以将任何东西加入列表中,其中的元素之间可以没有任何...

3585
来自专栏前端进阶之路

JS学习系列 06 - 变量对象

上一节我们讨论了执行上下文,那么在上下文中到底有什么内容,为什么它会和作用域链扯上关系,JS 解释器又是怎么找到我们声明的函数和变量,看完这一节,相信大家就不会...

842

扫码关注云+社区

领取腾讯云代金券