bawang51吧 关注:31贴子:3,169
  • 2回复贴,共1

【OI】randomqsort

只看楼主收藏回复

var a:array[1..100]of longint;
i,n:longint;
procedure swap(var x,y:longint);
var k:longint;
begin
x:=x xor y;
y:=x xor y;
x:=x xor y;
end;
procedure qsort(s,t:longint);
var i,j,x:longint;
begin
randomize;
x:=a[random(t-s)+s];
i:=s;
j:=t;
while i<=j do
begin
while (i<=j) and (a[j]>x) do j:=j-1;
while (i<=j) and (a[i]<x) do i:=i+1;
if i<=j then
begin
if i<j then
swap(a[i],a[j]);
j:=j-1;
i:=i+1;
end;
end;
if s<j then qsort(s,j);
if i<t then qsort(i,t);
end;
begin
readln(n);
for i:=1 to n do
readln(a[i]);
qsort(1,n);
for i:=1 to n do
writeln(a[i]);
end.



IP属地:上海1楼2011-10-19 21:06回复
    今天大家都以为是见鬼了,我平生第一次写随机化快排,输出一堆零。于是开始监控,发现swap有问题,我的swap是这样写的。
    procedure swap(var x,y:longint);
    begin
    x:=x xor y;
    y:=x xor y;
    x:=x xor y;
    end;
    没想到,交换的时候就都变零了,而xor 操作只有x=y时才会得0.
    最终发现,随机化快排有i=j的情况,此时 x:=x xor y;即a[i]:=a[i] xor a[i];
    a[i],a[j]都变为0.
    所以随机化快排要么不用位运算swap,要么i=j特判。


    IP属地:上海2楼2011-11-09 12:22
    回复
      2025-05-14 05:47:17
      广告
      1L代码位已经修正过的代码,可以直接使用。


      IP属地:上海3楼2011-11-09 12:25
      回复