急求PASCAL优化过的快速排序

优化过的快排就是随机化快排
快速排序是一种我们常用的排序方法，它的基本思想是递归式的：将待排序的一组数划分为两部分，前一部分的每个数不大于后一部分的每个数，然后继续分别对这两部分作划分，直到待划分的那部分数只含一个数为止。算法可由以下伪代码描述。
QUICKSORT(A,lo,hi)
1 if lo < hi
2 pPARTITION(A,lo,hi)
3 QUICKSORT(A,lo,p)
4 QUICKSORT(A,p+1,hi)
如果待排序的n个数存入了数组A，则调用QUICKSORT(A,1,n)就可获得升序排列的n个数。以上的快速排序的算法依赖于PARTITION(A,lo,hi)划分过程。该过程在(n)的时间内，把A[lo..hi]划分成不大于x=A[lo]，和不小于x=A[lo]的两部分。这两部分分别存入A[lo..p]和A[p+1,hi]。而在QUICKSORT(A,lo,hi)过程中递归调用QUICKSORT()，对A[lo..p]和A[p+1..hi]继续划分。
可以证明[4]，快速排序在最坏情况下(如每次划分都使p=lo)的时间复杂度为(n2)，在最好情况下的时间复杂度为(nlog2n)。如果假设输入中出现各种排列都是等概率的(但实际情况往往不是这样)，则算法的平均时间复杂度为O(nlog2n)。

随机化的快速排序
经分析我们看到，快速排序是十分有效的排序法，其平均时间复杂度为O(nlog2n)。但是在最坏情况下，它的时间复杂度为(n2)，当n较大时，速度就很慢(见本节后部的算法性能对照表)。其实，如果照前面的假设，输入中出现各种排列都是等概率的，那么出现最坏情况的概率小到只有(1/n!)，且在()中隐含的常数是很小的。这样看来，快速排序还是相当有价值的。
但是实际情况往往不符合该假设，可能对某个问题来说，我们遇到的输入大部分都是最坏情况或次坏情况。一种解决的办法是不用x=A[lo]划分A[lo..hi]，而用x=A[hi]或x=A[(lo+hi) div 2]或其它的A[lo..h