算法一直是计算机学科中一个非常核心的内容,学习大黑书可以让我们年轻人得到充沛的力量(也就是少点头发) , 在程序的海洋里快乐徜徉 。
排序算法是算法之中一个既基础又核心的内容 , 而快速排序则是比较排序中的佼佼者 。今天我们就一起来探究一下快速排序 。
普通快速排序
快速排序是一个经典的分治算法 , 解决分治问题的三个步骤就是 分解、解决、合并 。
拆开来看看快速排序的基本思想:
分解 :将输入数组A[l..r]划分成两个子数组的过程 。选择一个p,使得A被划分成三部分,分别是A[l..p-1],A[p]和A[p 1..r] 。并且使得A[l..p-1]中的元素都小于等于A[p],同时A[p]小于等于A[p 1..r]中的所有元素 。
解决:递归调用快速排序 , 解决分解中划分生成的两个子序列的排序 。
合并:因为子数组都是原址排序的,所以无需进行合并操作,数组A[p..r]已经有序 。
算法导论书上给出了简单易懂的伪代码,我在这直接给出的实现代码
def Quick_Sort(A,p,r):if p
这里看到数组的划分是直接选择了子数组的最后一个元素,那么当待排序列已经有序时,划分出的子序列便有一个序列是不含任何元素的,这使得排序的性能变差 。为了改善这种情况,我们可以选择引入一个随机量来破坏有序状态 。
快速排序的随机化版本
我们可以通过在选择划分时随机选择一个主元来实现随机快速排序 。仅需对上述代码做出小小的改动 。
def Quick_Sort_Random(A,p,r):if p
文章插图
性能比较
是骡子是马我们拉出来溜溜,我对两种快排的性能做了一个简单的测试 。首先是一定数量的随机序列,运行的时间单位为秒 , 下表中的结果是经多次运行所取得的平均值 。
方法$10^3$$10^4$$10^5$$10^6$$10^7$5*$10^7$$10^8$
普通快排
0.
0.
0.
4.
63.
456.
1176.
随机快排
0.
0.
0.
文章插图
5.
66.
451.
1108.
也可以使用可视化的方法将上表变得更加清楚,普通排序在数据量较小时具有一定的性能优势 , 随机快排可能是因为添加了随机选择这一项操作而影响了部分性能,但是随着数据量进一步增大 , 两者之间的性能会非常接近 。
接下来是对有序序列进行测试 ,
方法$10^3$$10^4$$10^5$$10^6$
【普通快排和随机快排的世纪大战】普通快排
0.
随机快排
0.
0.
7.
95.
普通快排在数据量非常小的时候就把栈给挤爆喽,从另一侧面反映出随机快排的必要性,在处理比较极端也就是完全有序的序列时具有较大的优势~
- 星河长明叶凌霜和翼无忧什么关系
- 张嘉倪买超感情时间线 张嘉倪和买超实际感情
- 张嘉倪和买超怎么认识的 张嘉倪与买超怎么认识
- 成都公积金贷款额度和缴存基数的关系
- 新鲜玉米和什么一起煮粥 新鲜玉米和什么一起煮粥好
- 黄瓜的营养和价值 黄瓜的营养价值有哪些?
- 苦瓜的药用价值和苦瓜的营养价值 苦瓜的药用功效和毒素
- 丝瓜的营养价值和药用价值 丝瓜的营养价值和医疗作用
- 北方地区如何栽培佛手瓜 北方佛手瓜的种植时间和种植要点
- 怎么区分田螺和福寿螺 田螺能吃吗