关于Pascal中的排序

Question

比如说 我要把由1*10^9个数从小到大排列，那一种排序用的时间最短？（希尔，冒泡，插入，快速，二分等等，只要是排序），在内存256M，CPU 2.0GHz的计算机上运算时间超过一秒吗？望给出算法

Answer 1

不用比如说了，一般排序是不会有这么大的数据的。一般用的是快排，但实际上堆排更快一些。

Program heapsort;

var a:array[1..100000] of longint;
n,i:longint;

procedure swap(var a,b:longint);
var t:longint;
begin
t:=a;
a:=b;
b:=t;
end;

procedure heap(i,n:longint);
var j,x:longint;
begin
x:=a[i];
j:=i*2;
while (j<=n) do
begin
if (j<n) and (a[j+1]>a[j]) then inc(j);
if x<a[j] then
begin
a[i]:=a[j];
i:=j;
j:=j*2;
end
else
break;
end;
a[i]:=x;
end;

begin
readln(n);
for i:=1 to n do read(a[i]);
for i:=n div 2 downto 1 do heap(i,n);
for i:=n downto 2 do
begin
swap(a[1],a[i]);
heap(1,i-1);
end;
for i:=1 to n-1 do write(a[i],' ');
writeln(a[n]);
end.

也可以用桶排，不过建议你可以看一看书，效率高的排序一般算法比较难理解的。

Answer 2

快速排序

var
i,j,sum,w,n:longint;
b:array[1..100000000] of longint;
procedure kp(l,r:longint);
var i,j,x,y:longint;
begin
i:=l;
j:=r;
x:=b[(i+j)div 2];
repeat
while b[i]<x do i:=i+1;
while b[j]>x do j:=j-1;
if not(i>j) then begin
y:=b[i];
b[i]:=b[j];
b[j]:=y;
i:=i+1;
j:=j-1;
end;
until i>j;
if i<r then kp(i,r);
if l<j then kp(l,j);
end;
begin
readln(w);
readln(n);
for i:=1 to n do readln(b[i]);
kp(1,n);
i:=1; j:=n+1; sum:=0;
repeat
inc(i);
dec(j);
if b[i]+b[j]<=w then begin
inc(sum);
inc(i);
dec(j);
end
else
inc(sum);
inc(j);
end;
until i=j
end.

Answer 3

其实在这里快排、堆排、桶排差不多，希尔慢那么一点点，冒泡估计要n天或月吧

Answer 4

pascal一定超，pascal不可能开多进程复杂度近30亿，
用c，开多进程加堆排+合并排序，256M是妄想。