快速排序算法交流

ABC23

快速排序算法的核心是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这样的三部分划分？

膜法记者

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

排序算法的效率有时候还跟语言有关。比如某种语言交换数值慢而比较数值大小快，那么最好用比较次数多而交换次数少的算法。
以上都是我学习的时候在csdn博客上看来的，有可能存在错误，若有怀疑请找百度