鱼C论坛

 找回密码
 立即注册
查看: 2430|回复: 1

[技术交流] 快速排序算法交流

[复制链接]
发表于 2018-4-24 16:49:12 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
快速排序算法的核心是partition(分割):
PARTITION(A, p, r)
        x = A[1]
        i = p-1
        for j = p to r-1
                if A[j] <= x
                        i = i + 1
                        exchange A[i] with A[j]
        exchange A[i+1] with A[r]
============================
上面就是PARTITION的伪代码部分。

关于快速排序有两点想要和大家讨论:
1. 第一个pivot(主元,基准点)必须取下表为r的点吗?虽然exchange A[i+1] with A[r] 在之后会改变主元的位置,但是能不能第一次就随机的在[p..r]中取一个值作为pivot呢?这样做和选取最后一个元素作为pivot想必有什么缺点?
2. 我们说quicksort的快,体现在平均时间性能上O(nlogn),如果在某个PARTITION调用中将元素划分为n-1、0、1三部分,将导致最坏情况,最坏时间复杂度为O(n^2)。在元素完全有序的条件下,时间复杂度为O(n^2),甚至不如插入排序O(n);什么样的条件将导致最坏情况的发生,或者说什么条件将导致n-1、0、1这样的三部分划分?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-4-24 18:12:06 | 显示全部楼层
本帖最后由 膜法记者 于 2018-4-24 18:18 编辑

1.可以随机取一个。有一种做法是比较第一个、最后一个、中间那个,取中位数作为基准
2.最坏情况你自己不是说出来了吗完全有序的条件下最坏情况发生啊

排序算法的效率有时候还跟语言有关。比如某种语言交换数值慢而比较数值大小快,那么最好用比较次数多而交换次数少的算法。
以上都是我学习的时候在csdn博客上看来的,有可能存在错误,若有怀疑请找百度
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 00:47

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表