视频动画 | 什么是快速排序?

点击蓝色“五分钟学算法”关注我哟

加个“星标”,天天中午 12:15,一起学算法

视频动画 | 什么是快速排序?


快速排序属性
视频动画 | 什么是快速排序?


 

视频动画 | 什么是快速排序?

 

上一篇文章介绍了 冒泡排序和它的优化 。这次介绍的快速排序是冒泡排序演变而来的算法,比冒泡排序要高效的很多。

 

快速排序之所以快,是因为它使用了分治法。它虽然也是通过不断的比较和移动来实现排序的,只不过它的实现,增大了比较的距离和移动的距离。而冒泡排序只是相邻的比较和交换。

 

快速排序的思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。

 

从字面上感觉不到它的好处,我们通过一个示例来理解基本的快速排序算法,假设当前数组元素是:5, 1, 9, 3, 7, 4, 8, 6, 2。

 


基本的快速排序算法
视频动画 | 什么是快速排序?


 

初始状态:5, 1, 9, 3, 7, 4, 8, 6, 2

 

选择5作为一个基准元素,然后从右向左移动hight下标,进行基准元素和下标为hight的元素进行比较。

 

如果基准元素要大,则进行hight的左移一位;如果基准元素要小,则进行元素的交换。

 

在hight下标左移的过程中,我们目的是找出比基准元素小的,然后进行交换。

 

交换完之后,进行left的右移,找出比基准元素大的,找到则进行交换。

 


视频动画
视频动画 | 什么是快速排序?


 


Code
视频动画 | 什么是快速排序?


 

视频动画 | 什么是快速排序?

 


Result
视频动画 | 什么是快速排序?


 

发生交换 [2, 1, 9, 3, 7, 4, 8, 6, 5]

发生交换 [2, 1, 5, 3, 7, 4, 8, 6, 9]

发生交换 [2, 1, 4, 3, 7, 5, 8, 6, 9]

发生交换 [2, 1, 4, 3, 5, 7, 8, 6, 9]

算出枢轴值 5 和对应下标 4

发生交换 [1, 2, 4, 3, 5, 7, 8, 6, 9]

算出枢轴值 2 和对应下标 1

发生交换 [1, 2, 3, 4, 5, 7, 8, 6, 9]

算出枢轴值 4 和对应下标 3

发生交换 [1, 2, 3, 4, 5, 6, 8, 7, 9]

发生交换 [1, 2, 3, 4, 5, 6, 7, 8, 9]

算出枢轴值 7 和对应下标 6

算出枢轴值 8 和对应下标 7

 


优化枢轴的选取
视频动画 | 什么是快速排序?


 

举一个恰当的例子,假设数组元素是9,8,7,6,5,4,3,2,1。

 

进行hight左移的时候第一个就发生了交换,1,8,7,6,5,4,3,2,9。嗯看似效率蛮快,但是进行low右移的时候一个个做了不必要的计算,没有一个元素比枢轴值要大。和冒泡排序一样,这一趟进行了8次比较,时间复杂度达到最坏程度O(n^2)。和快排的O(nlongn)相悖。

 

那拿什么更好的方式选取枢轴值呢?

 

我看到网上都说是,随机选取一个数作为基准元素。嗯看似一个好的方法,但是和上面大概率出现的最坏情况还是有可能发生的。每次选取枢轴值都有可能是最大的或者最小的。如果是庞大的数据量第一个随机选到了最大的数,程序卡的半死不活的,只有kill掉再重新运行吗?

 

改进情况,取三数之中的中间数的一个数。什么意思呢?

 

就是在一组数中取三个关键数字,将中间数作为枢轴,一般可以取左端,右端和中间三个数,也可以随机选取。那你可能说了,要是三个数都是最小的或者都是最大的那什么办呢?

 

没错,这样选取还是会带来时间上的开销,并不证明选取到一个好的枢轴值。那要是取九数之中的中间数呢?

 

这当然不是采用随机取九个数然后再排序排一半取中间数那一个。

 

它是从数组中分三次取样,每次取三个数,三个样品中各取出中间数,然后在这三个中枢当中再取一个中间数作为枢轴。如果一次极端就算了,但是分三次取样还会碰到三次极端那显然是微乎其微的。这样的方法增加选到好的枢轴的概率。

 


优化不必要的交换
视频动画 | 什么是快速排序?


 

回到基本的快速排序算法,回顾上面的视频动画。我们可以发现,这其中发生了不必要的移动方式。

 

我们最终要求一趟选的枢轴值,大的数在它的右边,小的数在它左边。但是这个枢轴值每次符合条件去了不该去的地方。我认为它前面的地方不要动,等一趟完了就去自己该去的地方,减少时间上的消耗。

 


视频动画
视频动画 | 什么是快速排序?


 


Code
视频动画 | 什么是快速排序?


 

视频动画 | 什么是快速排序?

 


Result
视频动画 | 什么是快速排序?


 

发生交换 [5, 1, 2, 3, 7, 4, 8, 6, 9]

发生交换 [5, 1, 2, 3, 4, 7, 8, 6, 9]

发生交换 [4, 1, 2, 3, 5, 7, 8, 6, 9]

算出枢轴值 5 和对应下标 4

发生交换 [3, 1, 2, 4, 5, 7, 8, 6, 9]

算出枢轴值 4 和对应下标 3

发生交换 [2, 1, 3, 4, 5, 7, 8, 6, 9]

算出枢轴值 3 和对应下标 2

发生交换 [1, 2, 3, 4, 5, 7, 8, 6, 9]

算出枢轴值 2 和对应下标 1

发生交换 [1, 2, 3, 4, 5, 7, 6, 8, 9]

发生交换 [1, 2, 3, 4, 5, 6, 7, 8, 9]

算出枢轴值 7 和对应下标 6

算出枢轴值 8 和对应下标 7

 


优化递归操作
视频动画 | 什么是快速排序?


 

我们都知道,递归对性能是有一定影响的,quickSort函数尾部有两次递归操作。如果待排序的序列极为极端不平衡,递归的深度几乎接近于n的高度(没有了二分法的优势)。这样的时间复杂度也是达到了最坏的程度O(n^2),而不是平衡时的O(nlogn)。

 

时间慢也就算了,但是栈的大小也是有限的,每次递归操作都消耗一定的栈空间,函数的参数越多,每次递归调用参数耗费的空间也是越多。

 

如果能减少递归,性能也因此大大提高。

 

那拿什么方式优化递归操作呢?

 

来看下面代码。

 


Code
视频动画 | 什么是快速排序?


 

视频动画 | 什么是快速排序?

 


Result
视频动画 | 什么是快速排序?


 

发生交换 [2, 1, 9, 3, 7, 4, 8, 6, 5]

发生交换 [2, 1, 5, 3, 7, 4, 8, 6, 9]

发生交换 [2, 1, 4, 3, 7, 5, 8, 6, 9]

发生交换 [2, 1, 4, 3, 5, 7, 8, 6, 9]

算出枢轴值 5 和对应下标 4

发生交换 [1, 2, 4, 3, 5, 7, 8, 6, 9]

算出枢轴值 2 和对应下标 1

发生交换 [1, 2, 3, 4, 5, 7, 8, 6, 9]

算出枢轴值 4 和对应下标 3

发生交换 [1, 2, 3, 4, 5, 6, 8, 7, 9]

发生交换 [1, 2, 3, 4, 5, 6, 7, 8, 9]

算出枢轴值 7 和对应下标 6

算出枢轴值 8 和对应下标 7

 

执行结果之后和前面两个结果无异。这是一个很好的方法。我们把if改成while,然后一次递归之后,low已经没有用处了,所以把pivot+1赋值给low作为下一个参数。结果你也看到了,结果都相同。

 

因此采用迭代而不是递归的方法可以缩减堆栈深度,从而提高了整体性能。

———————–
公众号:五分钟学算法(ID:CXYxiaowu
博客:www.cxyxiaowu.com
知乎:程序员吴师兄
一个正在学习算法的人,致力于将算法讲清楚!
长按下图二维码关注,和你一起领悟算法的魅力

视频动画 | 什么是快速排序?

戳一下下方的小程序,24 小时一起学算法

原文始发于微信公众号(五分钟学算法):视频动画 | 什么是快速排序?

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 视频动画 | 什么是快速排序?

我还会在以下平台发布内容

GitHub 哔哩哔哩