快速排序算法交流
快速排序算法的核心是partition（分割）：PARTITION(A, p, r)
x = A
i = p-1
for j = p to r-1
if A <= x
i = i + 1
exchange A with A
exchange A with A
============================
上面就是PARTITION的伪代码部分。
关于快速排序有两点想要和大家讨论：
1. 第一个pivot（主元，基准点）必须取下表为r的点吗？虽然exchange A with A 在之后会改变主元的位置，但是能不能第一次就随机的在中取一个值作为pivot呢？这样做和选取最后一个元素作为pivot想必有什么缺点？
2. 我们说quicksort的快，体现在平均时间性能上O(nlogn)，如果在某个PARTITION调用中将元素划分为n-1、0、1三部分，将导致最坏情况，最坏时间复杂度为O(n^2)。在元素完全有序的条件下，时间复杂度为O(n^2)，甚至不如插入排序O(n)；什么样的条件将导致最坏情况的发生，或者说什么条件将导致n-1、0、1这样的三部分划分？ 本帖最后由 膜法记者 于 2018-4-24 18:18 编辑
1.可以随机取一个。有一种做法是比较第一个、最后一个、中间那个，取中位数作为基准
2.最坏情况你自己不是说出来了吗{:10_250:}完全有序的条件下最坏情况发生啊
排序算法的效率有时候还跟语言有关。比如某种语言交换数值慢而比较数值大小快，那么最好用比较次数多而交换次数少的算法。
以上都是我学习的时候在csdn博客上看来的，有可能存在错误，若有怀疑请找百度{:10_266:}
页:
[1]