快排问题

来源:百度知道 编辑:UC知道 时间:2024/06/05 12:27:58
procedure qsort(h,t:integer);
var
p,i,j:integer;
begin
i:=h;
j:=t;
p:=a[i];
repeat
while (a[j]>p) and (j>i) do j:=j-1;
if j>i then
begin
a[i]:=a[j];
i:=i+1;
while (a[i]<p) and (i<j) do i:=i+1;
if i<j then
begin
a[j]:=a[i];
j:=j-1;
end;
end;
until i=j;
a[i]:=p;
i:=i+1;
j:=j-1;
if i<t then qsort(i,t);
if j>h then qsort(h,j);
end;

procedure qsort(l,r:integer);
var mid,t:longint;
begin
mid:=(r+l) div 2;
i:=l;j:=r;
repeat
while w[i]<w[mid] do inc(i);
while w[j]>w[mid] do dec(j);
if i<=j then
begin
t:=w[i];w[i]:=w[j];w[j]:=t; inc(i);dec(j) end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;

这有两个快速排序。
问题是:
1.为什么第2个只过4组数据。第一个都能过?
2.第2个有什么遗漏的地方?或者第一个有什么增加的地方?
注:这只是程序中的一个模块。经过调试,我发现错在快排上了,第一个是通过者的快排,

首先如果没看错的话,程序1是快排的标准程序。我们当时学的、我背的就是这个程序。可我试验了一下,程序2结果也是对的,。老师当时说把分界选在哪里应该都是对的,两边同时开始应该结果更快。
但有两个问题不清楚:1.分界的值会随着i,j的变化而变化(始终与W[mid]做比较,W[mid]在变化),这个不会影响吗?2.i,j定义为全局变量,会不会影响过程的调用?
我现在上不了vijos,也没做过这道题。能不能把原题和给的例子一起发上来?或者你可以试试把数据变简单一点,自己用Debug-Add Watch单步执行,看看有没有收获