- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章PHP排序算法之快速排序(Quick Sort)及其优化算法详解由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.
本文实例讲述了PHP排序算法之快速排序(Quick Sort)及其优化算法。分享给大家供大家参考,具体如下:
基本思想:
快速排序(Quicksort)是对冒泡排序的一种改进。他的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行快速排序,整个排序过程可以递归进行,以达到整个序列有序的目的.
基本算法步骤:
举个栗子:
假如现在待排序记录是:
6 2 7 3 8 9 。
第一步、创建变量 $low 指向记录中的第一个记录,$high 指向最后一个记录,$pivot 作为枢轴赋值为待排序记录的第一个元素(不一定是第一个),这里:
第二步、我们要把所有比 $pivot 小的数移动到 $pivot 的左面,所以我们可以开始寻找比6小的数,从 $high 开始,从右往左找,不断递减变量 $high 的值,我们找到第一个下标 3 的数据比 6 小,于是把数据 3 移到下标 0 的位置($low 指向的位置),把下标 0 的数据 6 移到下标 3,完成第一次比较:
3 2 7 6 8 9 。
第三步、我们开始第二次比较,这次要变成找比 $pivot 大的了,而且要从前往后找了。递加变量 $low,发现下标 2 的数据是第一个比 $pivot 大的,于是用下标 2 ($low 指向的位置)的数据 7 和 指向的下标 3 ($high 指向的位置)的数据的 6 做交换,数据状态变成下表:
3 2 6 7 8 9 。
完成第二步和第三步我们称为完成一个循环.
第四步(也就是开启下一个循环)、模仿第二步的过程执行.
第五步、模仿第三步的过程执行.
执行完第二个循环之后,数据状态如下:
3 2 6 7 8 9 。
到了这一步,我们发现 $low 和 $high“碰头”了:他们都指向了下标 2。于是,第一遍比较结束。得到结果如下,凡是 $pivot(=6) 左边的数都比它小,凡是 $pivot 右边的数都比它大.
然后,对 、$pivot 两边的数据 {3,2} 和 {7,8,9},再分组分别进行上述的过程,直到不能再分组为止.
注意:第一遍快速排序不会直接得到最终结果,只会把比k大和比k小的数分到k的两边。为了得到最后结果,需要再次对下标2两边的数组分别执行此步骤,然后再分解数组,直到数组不能再分解为止(只有一个数据),才能得到正确结果.
算法实现:
主函数中,由于第一遍快速排序是对整个数组排序的,因此开始是 $low=0,$high=count($arr)-1.
然后 QSort() 函数是个递归调用过程,因此对它封装了一下:
从上面的 QSort()函数中我们看出,Partition()函数才是整段代码的核心,因为该函数的功能是:选取当中的一个关键字,比如选择第一个关键字。然后想尽办法将它放到某个位置,使得它左边的值都比它小,右边的值都比它大,我们将这样的关键字成为枢轴(pivot).
直接上代码:
组合起来的整个代码如下:
我们调用算法:
运行结果:
复杂度分析:
在最优的情况下,也就是选择数轴处于整个数组的中间值的话,则每一次就会不断将数组平分为两半。因此最优情况下的时间复杂度是 O(nlogn) (跟堆排序、归并排序一样).
最坏的情况下,待排序的序列是正序或逆序的,那么在选择枢轴的时候只能选到边缘数据,每次划分得到的比上一次划分少一个记录,另一个划分为空,这样的情况的最终时间复杂度为 O(n^2). 。
综合最优与最差情况,平均的时间复杂度是 O(nlogn). 。
快速排序是一种不稳定排序方法.
由于快速排序是个比较高级的排序,而且被列为20世纪十大算法之一。。。。如此牛掰的算法,我们还有什么理由不去学他呢! 。
尽管这个算法已经很牛掰了,但是上面的算法程序依然有改进的地方,下面具体讨论一下 。
快速排序算法优化 。
优化一:优化选取枢轴:
在前面的复杂度分析的过程中,我们看到最坏的情况无非就是当我们选中的枢轴是整个序列的边缘值。比如这么一个序列:
9 1 5 8 3 7 4 6 2 。
按照习惯我们选择数组的第一个元素作为枢轴,则 $pivot = 9,在一次循环下来后划分为{1,5,8,3,7,4,6,2} 和{ }(空序列),也就是每一次划分只得到少一个记录的子序列,而另一个子序列为空。最终时间复杂度为 O(n^2)。最优的情况是当我们选中的枢轴是整个序列的中间值。但是我们不能每次都去遍历数组拿到最优值吧?那么就有了一下解决方法:
1、随机选取:随机选取 $low 到 $high 之间的数值,但是这样的做法有些撞大运的感觉了,万一没撞成功呢,那上面的问题还是没有解决.
2、三数取中法:取三个关键字先进行排序,取出中间数作为枢轴。这三个数一般取最左端、最右端和中间三个数,也可以随机取三个数。这样的取法得到的枢轴为中间数的可能性就大大提高了。由于整个序列是无序的,随机选择三个数和从左中右端取出三个数其实就是同一回事。而且随机数生成器本身还会带来时间的开销,因此随机生成不予考虑.
出于这个想法,我们修改 Partition() 函数:
三数取中法对于小数组有很大可能能沟得出比较理想的 $pivot,但是对于大数组就未必了,因此还有个办法是九数取中法。。。。。.
优化二:优化不必要的交换:
现在假如有个待排序的序列如下:
5 1 9 3 7 4 8 6 2 。
根据三数取中法我们取 5 7 2 中的 5 作为枢轴.
当你按照快速排序算法走一个循环,你会发现 5 的下标变换顺序是这样的:0 -> 8 -> 2 -> 5 -> 4,但是它的最终目标就是 4 的位置,当中的交换其实是不需要的.
根据这个思想,我们改进我们的 Partition() 函数
在上面的改进中,我们使用替换而不是交进行操作,由于在这当中少了多次的数据交换,因此在性能上也是有所提高的.
优化三:优化小数组的排序方案:
对于一个数学科学家、博士生导师,他可以攻克世界性的难题,可以培育最优秀的数学博士,当让他去教小学生“1 + 1 = 2”的算术课程,那还真未必比常年在小学里耕耘的数学老师教的好。换句话说,大材小用有时会变得反而不好用.
也就是说,快速排序对于比较大数组来说是一个很好的排序方案,但是假如数组非常小,那么快速排序算法反而不如直接插入排序来得更好(直接插入排序是简单排序中性能最好的)。其原因在于快速排序用到了递归操作,在大量数据排序的时候,这点性能影响相对于它的整体算法优势而言是可以忽略的,但如果数组只有几个记录需要排序时,这就成了大炮打蚊子的大问题.
因此我们需要修改一下我们的 QSort() 函数:
PS:上面的直接插入排序算法大家可以参考:《PHP排序算法之直接插入排序(Straight Insertion Sort)》 。
在这里我们增加一个判断,当 $high - $low 不大于一个常数时(有资料认为 7 比较合适,也有认为 50 比较合适,实际情况可以是适当调整),就用直接插入排序,这样就能保证最大化的利用这两种排序的优势来完成排序工作.
优化四:优化递归操作:
大家知道,递归对性能时有一定影响的,QSort()函数在其尾部有两次递归的操作,如果待排序的序列划分极端不平衡(就是我们在选择枢轴的时候不是中间值),那么递归的深度将趋近于 n,而不是平衡时的 log₂n,这就不仅仅是速度快慢的问题了.
我们也知道,递归是通过栈来实现的,栈的大小是很有限的,每次递归调用都会耗费一定的栈空间,函数的参数越多,每次递归耗费的空间也越多,因此如果能减少队规,将会大大提高性能.
听说,递归都可以改造成循环实现。我们在这里就是使用循环去优化递归。(关于递归与循环大家可以参考知乎里面的讨论 《所有递归都可以改写成循环吗?》) 。
我们对QSort() 函数尾部递归进行优化:
在上面,我们使用循环替换递归,减少了之前一般的递归量。结果是一样的,但是采用循环而不是递归的方法可以缩减堆栈的深度,从而提高了整体性能.
好了、终于写完了。这篇博客基本上是 Copy 《大话数据结构》里面的内容,在这里总结出来不仅是一个记录,大家也可以从中获得很大的收获.
最后此篇关于PHP排序算法之快速排序(Quick Sort)及其优化算法详解的文章就讲到这里了,如果你想了解更多关于PHP排序算法之快速排序(Quick Sort)及其优化算法详解的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
如何更改循环中变量的名称?比如 number1 、 number2 、 number3 、 number4 ? var array = [2,4,6,8] func ap ( number1: Int
我想设置 View 的背景颜色并在一定延迟后将其更改为另一种颜色。这是我的尝试方式: print("setting color 1") self.view.backgroundColor = UICo
我在使用 express-session 时遇到问题。 session 数据不会在请求之间持续存在。 正如您在下面的代码中看到的那样,/join 路由设置了一些 session 属性,但是当 /sur
我试图从叶渲染器获得一个非常简单的结果,用于快速 Steam 的 for 循环。 我正在上传叶文件 HTML,因为它不接受此处格式正确的代码 - 下面的pizza.swift代码- import
你们中有人有什么好的链接可以与我分享吗?我正在寻找一个 FAST 程序员编辑器,它可以非常快速地打开包含超过 100, 000 行代码的文件?我目前正在使用记事本自动取款机,打开一个 29000 行长
我现在正在处理眼动追踪数据,因此拥有一个巨大的数据集(想想数百万行),因此希望有一种快速的方法来完成此任务。这是它的简化版本。 数据告诉您眼睛在每个时间点正在查看的位置以及我们正在查看的每个文件。 X
我是新手,想为计时器或其他设备选择提示音。 如何打开此列表,以选择其中一种声音? Alert sound list 最佳答案 您将无法在应用中使用系统声音。 但是,您可以包括自己的声音文件,并将其显示
我编写了以下代码来构建具有顺序字符串的数组。 它的工作方式与我预期的一样,但我希望它能更快地运行。有没有更有效的方法在PowerShell中产生我想要的结果? 我是PowerShell的新手,非常感谢
我有一个包含一些非唯一行的矩阵,例如: x 尝试 y <- rle(apply(x, 1, paste, collapse = " ")) # y$lengths is the vector con
我的函数“keyboardWillShown”有问题。所以我想要的是菜单打开时,菜单正好出现在键盘上方。它可以在Iphone 8 plus,8、7、6上完美运行。但是,当我在模拟器上运行Iphone
我正在尝试通过Swift 5中的HTTP get方法从API提取数据。它在启动时成功加载了数据,但是当我刷新页面时,它说“索引超出范围”,这是因为数据是不再会在我的日志中读取,因此索引中没有任何内容。
我想做什么: 从我的数据库中获取时间戳并将其转换为用户的时区。 我的代码: let tryItNow = "\(model.timestampName)" let format = D
给定字体名称和字体大小,如何查找字符串的宽度(CGFloat)? (目标是将UIView的宽度设置为足以容纳字符串的宽度。) 我有两个字符串:一个重复“1”,重复36次,另一个重复“M”,重复36次。
我正在尝试解析此JSON ["Items": ( { AccountBalance = 0; AlphabetType = 3; Description = "\U0631\U
我在UINavigationBar内放置了一个UILabel。 我想根据navigationBar的高度增加该标签的字体大小。当navigationBar很大时,我希望字体大小更大;当滚动并缩小nav
我想将用户输入限制为仅有效数字并使用以下内容: func textView(_ textView: UITextView, shouldChangeTextIn range: NSRange, rep
目前我有一个包含超过 100.000 张图像的数据库,它们大小不一或类似,但我想为我的公司制作以下内容: 我插入/上传一张图片,系统返回最有可能相同的图片。我不知道使用什么算法,但它需要快速。我可以预
在我的 swift 项目中,我有一个按钮,我想在标签上打印按下该按钮的时间。 如何解决这个问题? 最佳答案 添加到DHEERAJ的答案中,您只需在func press(sender: UIButton
我必须发表评论,尝试在解析中导入数组。然而,有一个问题。 当我尝试从 Parse 加载数组时,我的输出是 ("Blah","Blah","Blah")这是一个元组...而不是一个数组 TT... 如何
我的应用程序有一个名为 MyDevice 的类,我用它来与硬件通信。该硬件是可选的,实例变量也是可选的: var theDevice:MyDevice = nil 然后,在应用程序中,我必须初始化设备
我是一名优秀的程序员,十分优秀!