急求PASCAL优化过的快速排序

Question

我是搞竞赛的，快排我会，但是有些题专门针对快排出了类似倒序类的变态数据，比如去年NOIP提高第一题COUNT，我看见过有人用优化过的快排满分过了这道题，但是他不肯给我他的快排，于是就上网求助，马上就要开考了，帮哈忙，随机快排就免了。

Answer 1

优化过的快排就是随机化快排
快速排序是一种我们常用的排序方法，它的基本思想是递归式的：将待排序的一组数划分为两部分，前一部分的每个数不大于后一部分的每个数，然后继续分别对这两部分作划分，直到待划分的那部分数只含一个数为止。算法可由以下伪代码描述。
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..hi]中的数来划分A[lo..hi]，这要看具体情况而定。但这并没有解决问题，因为我们可能遇到的这样的输入：有三类，每一类出现的概率为1/3，且每一类分别对于x=A[lo]，x=A[hi]，x=A[(lo+hi) div 2]为它们的最坏情况，这时快速排序就会十分低效。
我们将快速排序随机化后可克服这类问题。随机化快速排序的思想是：每次划分时从A[lo..hi]中随机地选一个数作为x对A[lo..hi]划分。只需对原算法稍作修改就行了。我们只是增加了PARTITION_R函数，它调用原来的PARTITION()过程。QUICKSORT_R()中斜体部分为我们对QUICKSORT的修改。
PARTITION_R(A,lo,hi)
1 rRANDOM(hi-lo+1)+lo
2 交换A[lo]和A[r]
3 return PARTITION(A,lo,hi)

QUICKSORT_R(A,lo,hi)
1 if lo < hi
2 pPARTITION_R(A,lo,hi)
3 QUICKSORT_R(A,lo,p)
4 QUICKSORT_R(A,p+1,hi)

分析随机化快速排序算法
随机化没有改动原来快速排序的划分过程，故随机化快速排序的时间效率依然依赖于每次划分选取的数在排好序的数组中的位置，其最坏，平均，最佳时间复杂度依然分别为(n2)，O(nlog2n)，(nlog2n)，只不过最坏情况，最佳情况变了。最坏，最佳情况不再由输入所决定，而是由随机函数所决定。也就是说，我们无法通过给出一个最坏的输入来使执行时出现最坏情况(除非我们运气不佳)。
正如引论中所提到的，我们现在来分析随机化快速排序的稳定性。按各种排列的出现等概率的假设(该假设不一定成立)，快速排序遇到最坏情况的可能性为(1/n!)。假设RANDOM(n)产生n个数的概率都相同(该假设几乎一定成立)，则随机化快速排序遇到最坏情况的可能性也为(1/n!)。如果n足够大，我们就有多于99%的可能性会“交好运”。也就是说，随机化的快速排序算法有很高的稳定性。

引自<论随机化算法的原理与设计>周咏基

Answer 2

拜托！一般的就够了！！！！

Codes：
var i,j,k,m,n,tot:longint;
a:array[0..200000] of longint;
procedure qsort( s,t:longint);
var i,j,k,temp,p:longint;
begin
if s>=t then exit;
p:=s+(t-s)div 2;
i:=s;j:=t;
temp:=a[p];a[p]:=a[s];
repeat
while(i<j) and(a[j]>=temp) do
dec(j);
if i=j then break;
a[i]:=a[j];
inc(i);
while (i<j) and(a[i]<=temp) do
inc(i);
if i=j then break;
a[j]:=a[i];
dec(j);
until i=j;
a[i]:=temp;
qsort(s,i-1);qsort(i+1,t);
end;
begin
assign(input,'count1.in');reset(input);
assign(output,'count.out');rewrite(output);
readln(n);
for i:=1 to n do readln (a[i]);
qsort(1,n);
a[0]:=a[1];
write(a[1],' ');
for i:=1 to n do begin
if a[i]<>a[i-1] then begin
write(tot);
tot:=0;
writeln;
write(a[i],' ');
end;
inc(tot);
end;
write(tot);
end.