急求PASCAL优化过的快速排序

pascal编程：快速排序~

var a:array[1..100000]of longint; n,i:longint;
procedure qsort(l,r: longint);
var i,j,x,y: longint;
begin
i:=l; j:=r; x:=a[(l+r) div 2];
repeat
while a[i]<x do inc(i);
while x<a[j] do dec(j);
if not(i>j) then
begin
y:=a[i]; a[i]:=a[j]; a[j]:=y;
inc(i); j:=j-1;
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
begin
assign(input,'sort.in'); reset(input);
assign(output,'sort.out'); rewrite(output);
readln(n);
for i:=1 to n do read(a[i]);
qsort(1,n);
write(a[1]);
for i:=2 to n do write(' ',a[i]);
writeln;
close(input); close(output);
end.

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：

1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；

2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；

3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；

4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；

5）、重复第3、4步，直到I>j；

详细过程举例如下：
原序： [26 5 37 1 61 11 59 15 48 19]
一： [19 5 15 1 11] 26 [59 61 48 37]
二： [11 5 15 1] 19 26 [59 61 48 37]
三： [1 5] 11 [15] 19 26 [59 61 48 37]
四： 1 5 11 [15] 19 26 [59 61 48 37]
五： 1 5 11 15 19 26 [59 61 48 37]
六： 1 5 11 15 19 26 [37 48] 59 [61]
七： 1 5 11 15 19 26 37 48 59 [61]
八： 1 5 11 15 19 26 37 48 59 61

























快速排序法是所有排序方法中速度最快、效率最高的方法。程序如下：
var a:array[0..10] of integer；
n:integer;
procedure qsort(l,r:longint);{r，l表示集合的左右边界，即把第r到第l个数进行排序}
var i,j,m:longint;
begin
m:=a[l];{标准数}
i:=l; {I，J为指针}
j:=r;
repeat
while a[i]<m do inc(i);
while a[j]>m do dec(j);
if i<=j then begin
a[0]:=a[i];
a[i]:=a[j];
a[j]:=a[0];
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j); {如果集合中不止一个数则进入下一层递归，l，J为新边界}
if i<rthen qsort(i,r); {如果集合中不止一个数则进入下一层递归，i，r为新边界}
end;
begin
for n:=1 to 10 do read(a[n]);
qsort(1,10);
for n:=1 to 10 do write(a[n]:4);
end.

优化过的快排就是随机化快排
快速排序是一种我们常用的排序方法，它的基本思想是递归式的：将待排序的一组数划分为两部分，前一部分的每个数不大于后一部分的每个数，然后继续分别对这两部分作划分，直到待划分的那部分数只含一个数为止。算法可由以下伪代码描述。
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%的可能性会“交好运”。也就是说，随机化的快速排序算法有很高的稳定性。

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

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

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.

---

潍城区19192241167： 急求PASCAL优化过的快速排序 - ？
家依益迈： 优化过的快排就是随机化快排 快速排序是一种我们常用的排序方法,它的基本思想是递归式的:将待排序的一组数划分为两部分,前一部分的每个数不大于后一部分的每个数,然后继续分别对这两部分作划分,直到待划分的那部分数只含一个数...

潍城区19192241167： 简化的pascal快速排序代码 - ？
家依益迈： 我背的就是这个,特别好用,还好记.procedure quicksort(l,r:longint); var __x,i,j,t :longint; begin __x:=a[random(r-l+1)+l]; __i:=l;j:=r; __repeat ____while a[i]<x do inc(i); ____while a[j]>x do dec(j); ____if i<=j then ______begin ________t:=a[i]; a[i]:=a...

潍城区19192241167： Pascal中最快的排序法是什么?？
家依益迈： 堆排序,归并排序,快速排序都是最快速的排序算法,这三者都是O(NLOG2N)的;理论上基于比较的排序算法是无法超越这个极限的; 而这三者,相对比来说: 快排最好写,但不稳定; 堆排稍微长点,也不稳定; 归并排序代码不算长,是稳定的,但是需要额外的数组来临时存储; 我比较推荐快速排序,随机化加不加都行; 如果数据是限定在某一个小区间内的话,你还可以应用计数排序,这个算法是线性的.

潍城区19192241167： 求快速排序的pascal代码和详细解答 - ？
家依益迈： 程序1:program kspv; const n=7; type arr=array[1..n] of integer; var a:arr; i:integer; procedure quicksort(var b:arr; s,t:integer); var i,j,x,t1:integer; begin i:=s;j:=t;x:=b[i]; repeat while (b[j]>=x) and (j>i) do j:=j-1; if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end; ...

潍城区19192241167： pascal中的快排 - ？
家依益迈： {快排(小到大)}var a:array[1..100]of longint;i,n:longint;procedure kp(s,t:longint); var i,j,x,t1:longint; begini:=s;j:=t;x:=a[i];repeatwhile (a[j]>=x) and (j>i) do dec(j);if j>i then begint1:=a[i];a[i]:=a[j];a[j]:=t1;end;while (a[i]<=x) and (i<j) do inc(i...

潍城区19192241167： pascal的快速排序,堆排序的例子(或源代码) - ？
家依益迈： 快排 procedure qsort ( l , r : longint ); vari , j , m , t : longint; begini := l;j := r;m := ans [ ( i + j ) div 2 ];repeatwhile ans [ i ] < m do inc ( i );while ans [ j ] > m do dec ( j );if i <= j thenbegint := ans [ i ];ans [ i ] := ans [ j ];ans [ j ] := t;inc ( i );dec ( ...

潍城区19192241167： Pascal的快排代码 - ？
家依益迈： ls 是冒泡吧?没见过这样的快排.....真正的快排应该是这样的(假设被排序的数组是a,且快排后按升序排列):procedure qsort(l,h:integer); var i,j,t,m:integer; begin i:=l; j:=h;m:=a[(i+j) div 2]; //注意:本句不能写成:m:=(i+j) div 2;repeat while a[i]...

潍城区19192241167： 用pascal编快速排序？
家依益迈： 快排-单关键字 procedure qsort(l,r:longint); var i,j,k,x:longint; begin i:=l;j:=r;x:=a[(i+j) div 2]; repeat while a[i]<x do inc(i); while a[j]>x do dec(j); if i<=j then begin k:=a[i];a[i]:=a[j];a[j]:=k; inc(i);dec(j); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j); end;...

潍城区19192241167： 快速排序的例子,要pascal的,谢谢大家了~~~!？
家依益迈： 快排只是思想、方法,种类很多的,复制个最基本的给你(你没买书啊?):Program quiksort; //快速排序法 const max=100; var n:integer; a:array[1..max] of longint; procedure sort(l,r: longint); var i,j,x,y: longint; begin i:=l; j:=r; x:=a[(l+r) ...

潍城区19192241167： 谁有pascal的快排程序啊,拜求 - ？
家依益迈： var a:array[1..100] of longint; i,n:longint; procedure qsort(s,e:longint); var i,j,mid,temp:longint; begin i:=s;j:=e;mid:=a[(i+j) div 2]; while i begin while a[i] while a[j]>mid do j:=j-1; if i begin temp:=a[i];a[i]:=a[j];a[j]:=temp; i:=i+1;j:=j-1; end; end; if s if iend; ...