回 帖 发 新 帖 刷新版面

主题:[讨论]快速排序 请找一下错误

program kspx;
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;
      while (b[i]<=x) and (i<j) do i:=i+1;
      if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1;end;
    until i=j;
    b[i]:=x;
    if s<j then quicksort (b,s,j);
    if i<t then quicksort (b,i,t);
  end;
begin
     write('input data:');
     for i:=1 to n do read(a[i]);
     writeln;
     quicksort(a,1,n);
     write('output data');
     for i:=1 to n do write(a[i]:6);
     writeln;
end.

这是我看资料上的快速排序,运行不起来
请各位找一下错误
如果有人愿意,请讲解一下
  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;
      while (b[i]<=x) and (i<j) do i:=i+1;
      if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1;end;
    until i=j;
这段程序的作用和原理

回复列表 (共8个回复)

沙发

错误我就懒得找了,标准程序如下:
procedure  quicksort(var a:arr;s,t:integer);
var I,j:integer;
begin 
  i:=s;j:=t;x:=a[s];
  while  i<j   do
        begin
           while  (a[j]>=x) and (j>i)  do  j:=j-1;
           if  j>i  then  begin  a[i]:=a[j];i:=i+1;  end;
           while  ( a[i]<=x) and (i<j)  do i:=i+1;
           if  i<j  then  begin  a[j]:=a[i];j:=j-1  end;
        end;
  a[i]:=x;
  if s<(i-1)  then  quicksort(a,s,i-1);
  if t>(i+1)  then   quicksort(a,i+1,t);
end;                        

板凳

可不可以把程序都打全啊
怎么会和我的不一样呢
还有,能解释一下中间的语句吗

3 楼

因为听初二的同学说快排每年都会间接地考到
所以各位,一定要帮帮我
或者发上来全的源程序也行
求求拉!!!

4 楼

楼主的quicksort那一段:
  begin后要加上 if s=t then exit;
  否则递归调用会一直进行下去。
  
Repeat那一段:
   快排的思想是以序列中某个中间数(b[i])为标准,把所有比它大的数放在一边,比它小的数放在另一边。然后对两边继续照这样处理。注意边界是待处理的序列只有一个数,
也就是s=t

   具体来说,对于程序中Repeat...until中的两个指针i,j。
   j从大往小找,找到右边第一个比x小的元素与b[i]交换,实际上b[i]是临时变量,
而保存这个中间数的是x,这样b[j]这个比x小的数就到了左边
   i从小往大找,找到左边第一个比x大的元素与临时变量b[j]交换。
   这样直到比x大的数到了右边,小的到了左边为止,即i=j。这时i就是x应该放的位置。

5 楼

非常感谢
我今天到NOIP的网站上看了看日程,好激动啊!!!
但是碍于水平问题,又好害怕啊~~

6 楼

可是那样子写还是不能通过.
b[i]=x的后面应该加上
i:=i+1;j:=j-1;
快排有很多版本,是我不小心看错了,对不起[em12].( 其实以前学快排我就是背的这个程序.)

7 楼

告诉大家一个秘密:完整版的 Turbo Pascal 7.0 附带快速排序的超标准程序!!
程序文件在 TP 文件夹中的 EXAMPLES 文件夹中,文件名为 QSORT.PAS 
如果竞赛用的机子装有完整版TP,那就……哈哈哈哈……!!!

8 楼

可是我们考试好象是用FP啊!
不过FP的数组空间很大,很好,可是……没有这个程序也是一种损失啊

我来回复

您尚未登录,请登录后再回复。点此登录或注册