算法之12 | 快速排序 快速排序算法例题及答案
yuyutoo 2024-10-12 01:09 6 浏览 0 评论
1. 算法描述
快速排序(quick-sort)与前面介绍的归并排序(merge-sort)一样,使用了分治思想。下面是对一个一般的子数组A[p~r]进行快速排序的分治步骤:
① 分解:数组A[p~r]被划分为两个子数组A[p~q]和A[q+1~r],使得 A[q] 大于等于 A[p~q] 中的每个元素,且小于等于 A[q+1~r] 中的每个元素。(需要注意的是, A[p~q] 和 A[q+1~r] 可能为空)
② 解决:对子数组 A[p~q] 和 A[q+1~r] 递归调用本程序。
③ 合并:因为子数组都是原址排序的,所以不需要合并操作,此时的A数组已经是排好序的。
ps:所谓原址排序是指:在对组进行排序的过程中,只有常数个元素被存储到数组外面。
快速排序的核心思想其实很简单,即:在数组中,如果某元素均比自己前面的元素大(或等于),而比自己后面的元素小(或等于),则该元素处于“正确位置”。
下面给出伪代码:
可以看出,算法的关键是partiton方法的实现。下面给出它的算法实现:
直接看可能觉得很晕,我们结合实例看看它是如何工作的:
上图(a~i)表示的是对子数组A[p~r] =[2,8,7,1,3,5,6,4]进行排序时,每次迭代之前数组元素和一些变量的值。
我们可以初步看出,在i和j移动的过程中,数组被分成了三个部分(分别用灰色,黑色,白色表示),其中i和j就是分割线,并且浅灰部分的元素均比A[r]小,黑色部分的元素均比A[r]大((i)图除外,因为循环完毕之后执行了exchange A[i+1] with A[j])。
我们再仔细分析一下具体细节:
① 首先看迭代之前的部分。它执行了x = A[r],目的是把子数组A的最后一位作为一个“基准”,其他的所有元素都是和它进行比较。它在迭代过程中值一直都没改变。然后执行i = p –基准 1,此时i在子数组A的左端。
② 再看迭代部分。迭代时j从子数组A的开头逐步移至A的倒数第二位。每次迭代中,会比较当前j位置的值和“基准”的大小,如果小于或相等“基准”,就将灰色部分的长度增加1(i=i+1),然后把j位置的值置换到灰色部分的末尾(exchange A[i] with A[j])。这样迭代下来,就能保证灰色部分的值都比“基准”小或相等,而黑色部分的值都比“基准”大。
③ 最后看迭代完成后的部分。就进行了一步 exchange A[i+1] with A[j]操作,就是把“基准”置换到灰色部分与黑色部分之间的位置。
这样所有的操作下来,就产生了一个“临界”位置q,使得A[q]大于等于A[p~q]中的每个元素,而小于等于A[q+1~r]中的每个元素。
更严格的,我们可以用以前介绍的循环不变式来证明其正确性。但由于叙述起来比较麻烦,这里就不给出了。
下面我们给出快速排序(quick-sort)算法的Java实现代码:
public static void main(String[] args) {
int[] array = { 9, 2, 4, 0, 4, 1, 3, 5 };
quickSort(array, 0, array.length - 1);
printArray(array);
}
/**
* 快速排序
*
* @param array
* 待排序数组
* @param start
* 待排序子数组的起始索引
* @param end
* 待排序子数组的结束索引
*/
public static void quickSort(int[] array, int start, int end) {
if (start < end) {
int position = partition(array, start, end);
quickSort(array, start, position - 1);
quickSort(array, position + 1, end);
}
}
/**
* 重排array,并找出“临界”位置的索引
*
* @param array
* 待重排数组
* @param start
* 待重排子数组的起始索引
* @param end
* 待重排子数组的结束索引
* @return
*/
public static int partition(int[] array, int start, int end) {
int position = start - 1;
int base = array[end];
for (int i = start; i < end; i++) {
if (array[i] <= base) {
position++;
int temp = array[position];
array[position] = array[i];
array[i] = temp;
}
}
int temp = array[position + 1];
array[position + 1] = array[end];
array[end] = temp;
return position + 1;
}
/**
* 打印数组
*
* @param array
*/
public static void printArray(int[] array) {
for (int i : array) {
System.out.print(i + "");
}
System.out.println();
}
结果:
2. 快速排序的性能
快速排序的运行时间是跟划分密切相关的,因为划分影响着子问题的规模。
(1) 最坏情况划分
当每次划分把问题分解为一个规模为n-1的问题和一个规模为0的问题时,快速排序将产生最坏的情况(以后给出这个结论的证明,目前可以想象的出)。由于划分操作的时间复杂度为θ(n);当对一个长度为0的数组进行递归操作时,会直接返回,时间为T(0) = θ(1)。于是算法总运行时间的递归式为:
T(n) = T(n-1) + T(0) + θ(n) = T(n-1) + θ(n) 。
可以解得,T(n) = θ(n2)。
由此可见,在划分都是最大程度不平均的情况下,快速排序算法的运行时间并不比插入排序好,甚至在某些情况下(比如数组本身已按大小排好序),不如插入排序。
(2) 最好情况划分
当每次划分都是最平均的时候(即问题规模被划分为[n/2]和【n/2】-1时),快速排序性能很好,总运行时间的递归式为:
T(n) = 2T(n/2) + θ(n)
可以解得,T(n) = θ(nlg n)。
(3) 平均划分
快速排序算法的平均运行时间,更接近于最好情况划分时间而非最坏情况划分时间。理解这一点的关键就是理解划分的平均性是如何反映到描述运行时间的递归式上的。
我们举个例子,对于一个9:1的划分,乍一看,这种划分是很不平均的。此时的运行时间递归式为:
T(n) = T(9n/10) + T(n/10) + cn,
我们可以用如下递归树来更加形象地描述运行时间:
递归会在深度为log10/9n = θ(lg n )处终止,因此,快速排序的总代价为O(nlgn)。可见,在直观上看起来非常不平均的划分,其运行时间是接近最好情况划分的时间的。事实上,对于任何一种常数比例的划分,其运行时间总是O(nlgn)。
3. 快速排序的随机化版本
以上的讨论其实都做了一个前提的声明,输入数据的所有排列都是等概率的。但是事实上这个条件并不一定总是成立。正如以前介绍的,有时候我们再在算法中引入随机性,可以使得算法对所以的输入都有较好的期望性能。很多人都选择随机化版本的快速排序作为大数据输入情况下的排序算法。
我们可以使用对数组的所有元素进行随机化排序的方式引入随机性。但为了简便,我们这里采用一种叫做随机抽样(random sampling)的随机化技术。
与以上始终采用A[r]作为“基准”的方法不同的是,随机抽样是从子数组A[p~r]中随机的抽取一个元素,把它作为“基准”,并与A[r]交换。其他的过程与上面介绍的一致。
下面是随机化版本的算法描述:
下面给出随机化版本的Java实现代码:
public static void main(String[] args) {
int[] array = { 9, 2, 4, 0, 4, 1, 3, 5 };
randomizedQuickSort(array, 0, array.length - 1);
printArray(array);
}
public static int randomPartition(int[] array, int start, int end) {
int random = (int) (Math.random() * ((end - start) + 1)) + start;
int temp = array[random];
array[random] = array[end];
array[end] = temp;
return partition(array, start, end);
}
/**
* 快速排序
*
* @param array
* 待排序数组
* @param start
* 待排序子数组的起始索引
* @param end
* 待排序子数组的结束索引
*/
public static void randomizedQuickSort(int[] array, int start, int end) {
if (start < end) {
int position = randomPartition(array, start, end);
randomizedQuickSort(array, start, position - 1);
randomizedQuickSort(array, position + 1, end);
}
}
运行结果:
4. 快速排序分析
在第2小节中我们给出了快速排序性能的直观分析,以及它速度比较快的原因。这一节我们要给出一个更加严谨的分析。
(1) 最坏情况分析
我们用T(n)来表示规模为n的数组采用快速排序法排序所需的时间。PARTION函数生成的两个子数组的总长度是n-1,我们设其中一个的长度为q(0 ≤ q ≤ n-1),那么另一个的长度为n-q-1,因此有递归式:
我们容易知道,上式中q在端点上取得最大值。由此我们得到:
因此,T(n) = θ(n2) + θ(n) = θ(n2);
这就是说,快速排序算法的最坏情况的运行时间是θ(n2);
(2) 期望运行时间
现在我们要求,在平均情况下,快速排序的运行时间。因此我们先对问题进行分析。
从算法的描述中我们可以看出,快速排序的运行时间是由在PARTITION操作上花费的时间决定的。每一次PARTITION操作都会从数组中挑选出一个数作为“基准”,因此PARTITION操作的总次数不会超过数组元素的总个数n。而每一次PARTITION操作的时间包括O(1)加上一段循环的时间。而在该循环的每次迭代中,都会比较“基准”元素与其他元素。因此,如果我们可以统计出总的比较次数(注意这里所说的比较次数是整个快速排序过程中比较的次数),就能够知道该循环的运行时间,从而就能给出快速排序的运行时间。
为了便于分析,不失一般性,我们将数组A的各个元素重命名为Z1,Z2,…Zn,其中Zi表示数组A中第i小的元素;此外我们还定义Zij表示一个包含元素Zi到Zj(包括Zi和Zj)的集合,即Zij={Zi,Zi+1,…Zj}。
和概率分析和随机算法(2)——算法导论(6)中方式①介绍的方法一样,我们引入一个指示器随机变量Xij来表示Zi与Zj是否进行了比较,即:
因为每一对元素至多被计较一次,因此我们可以很容易算出总比较次数为:
对上式两边取期望得:
下面我们来分析如何求P(zi与zj进行比较)。
我们先从一个简单的例子入手。考虑对一个包含数字1~10的数组A进行快速排序的情况。假设我们第一次进行PARTITION操作时,选定的“基准”元素是7,那么数组A将被划分为{1,2,3,4,5,6}和{8,9,10}两个数组,我们可以发现,这两个数组中彼此任何两个元素是不会相互比较的。因此,我们有如下断言:如果一个满足zi < X < zj(假设各元素互异)的元素x被选为“基准”后,zi 和zj就不会被比较了;如果zi在Zij的其他元素之前被选为“基准”,那么zi会与Zij中的其他所有元素进行比较。于是有:
进而得到:
由此我们可以得出结论:使用RANDOMIZED-PARTITION,在输入元素互异的情况下,快速排序算法的期望运行时间是O(nlgn)。
注:凡属于本公众号内容,未经允许不得私自转载,否则将依法追究侵权责任。
相关推荐
- 国产RISC-V终端Sipeed Lichee Console4A上架,1699元起
-
IT之家12月11日消息,国内著名开源硬件厂商Sipeed矽速科技推出RISC-V终端LicheeConsole4A,售价1699元(不带LM4A模块)-3299元。Li...
- H3C交换机常用配置命令
-
1、配置主机名...
- ThinkPad老版Bios中英文对应详解
-
ThinkPad老版Bios中文对应详解。解决方案:...
- 澳大利亚Console Connect与非洲数据中心达成战略合作,增强整个非洲的数据连接
-
据techafricanews网11月13日报道,在2024年非洲科技节上,澳大利亚ConsoleConnect与非洲数据中心共同宣布了一项具有里程碑意义的战略合作协议,该协议致力于提升非洲大陆关键...
- 多功能调焦 腾龙TAP-in Console延期发售
-
最新消息传出,腾龙TAP-inConsole(modeltap-01)多功能调焦器由于生产方面原因原本预计3月24日发售延迟至3月30日,腾龙的这款调焦器功能类似于适马的USBDock调焦底座,...
- 关于交换机上存在的不同接口介绍(一)
-
生活中常见的电子设备有很多,其中明交换机主要起到的是连接的作用,上面有非常多的接口,下面就一起来看看这些不同的接口作用是什么。1、RJ-45接口这是我们见的最多、应用最广的一种接口类型,它属于双绞线以...
- 颜值更高?微软新推精英版Xbox One手柄
-
本月,微软的XboxOne升级了更强大的版本——XboxOneEliteconsole(精英版?),升级版的控制手柄功能更强大,可以主导你的客厅;从曝光的图片上看得出,新版XboxOneE...
- “全球首个”:Console Connect为全球物联网项目推出连接解决方案
-
据DevelopingTelecoms2月27日报道,在MWC2023上,全球网络即服务(NaaS)平台ConsoleConnect推出了“全球首个”私有连接解决方案,可帮助企业在全球范围内动态...
- 密码遗忘专题——Console口密码遗忘
-
如果忘记了Console口密码,用户可以通过以下两种方式来设置新的Console口密码:方法一:通过STelnet/Telnet登录设备修改Console口密码。...
- 为锐捷路由器交换机开启web和telnet,实现轻松管理
-
笔者上一篇文章写了关于锐捷二层交换机配置教程,那么接下来讲一下锐捷的路由交换设备配置web、telnet技巧。同样,今天的教程也是基于命令行,比较简单,适合新手小白进行学习。准备工作配置前准备:con...
- C# - 类文件构成,C#基本语法,Console属性与方法 007
-
类文件(.cs)构成类文件主要分为引用命名空间与自己项目的命名空间...
- Console OS系统帮你在PC上自由切换Windows和安卓应用
-
通过ConsoleOS你可以在你的PC上安装自己喜欢的安卓游戏,需要时之间切换回Windows进行其他工作,ConsoleOS能够完全利用你的PC硬件配置,该系统可以安装在PC的内置硬盘里,也可以...
- 交换机通过串口线console口登录设备
-
一、功能简介:PC端通过设备的Console口登录,实现对第一次上电的设备进行基本配置和管理。...
- (每日持续更新)jdk api之Console基础、应用、实战
-
博主18年的互联网软件开发经验,从一名程序员小白逐步成为了一名架构师,我想通过平台将经验分享给大家,因此博主每天会在各个大牛网站点赞量超高的博客等寻找该技术栈的资料结合自己的经验,晚上进行用心精简、整...
- KFC推出“真正的次世代主机”KFConsole!真4K/120帧
-
今天KFCGaming官方推特发布了一则“主机”宣传片,正式公布了旗下名为KFConsole的全新主机产品。并宣称:游戏的未来就在这里,介绍真正的次世代主机!根据官方介绍,本款KFC主机功能强大,支...
你 发表评论:
欢迎- 一周热门
-
-
前端面试:iframe 的优缺点? iframe有那些缺点
-
带斜线的表头制作好了,如何填充内容?这几种方法你更喜欢哪个?
-
漫学笔记之PHP.ini常用的配置信息
-
推荐7个模板代码和其他游戏源码下载的网址
-
其实模版网站在开发工作中很重要,推荐几个参考站给大家
-
[干货] JAVA - JVM - 2 内存两分 [干货]+java+-+jvm+-+2+内存两分吗
-
正在学习使用python搭建自动化测试框架?这个系统包你可能会用到
-
织梦(Dedecms)建站教程 织梦建站详细步骤
-
【开源分享】2024PHP在线客服系统源码(搭建教程+终身使用)
-
2024PHP在线客服系统源码+完全开源 带详细搭建教程
-
- 最近发表
- 标签列表
-
- mybatis plus (70)
- scheduledtask (71)
- css滚动条 (60)
- java学生成绩管理系统 (59)
- 结构体数组 (69)
- databasemetadata (64)
- javastatic (68)
- jsp实用教程 (53)
- fontawesome (57)
- widget开发 (57)
- vb net教程 (62)
- hibernate 教程 (63)
- case语句 (57)
- svn连接 (74)
- directoryindex (69)
- session timeout (58)
- textbox换行 (67)
- extension_dir (64)
- linearlayout (58)
- vba高级教程 (75)
- iframe用法 (58)
- sqlparameter (59)
- trim函数 (59)
- flex布局 (63)
- contextloaderlistener (56)