『求助』排序算法 [复制链接]

网上把排序算法超的很热，说的靠复赛必须背快排，为什么哦？？举例说明下嘛，大牛们！！

type sun=array[0..1000（或其它）]of longint（或byte,integer,int64,shortint，但注意的类型应随之改变）
procedure qsort(var a:sun;m,n:integer);
  var i:integer;
  function slipt(var a:sun;m,n:integer):integer;
    var i,j,k:integer;
      t:longint;
    begin
    k:=n-m+1;
    k:=random(k)+m;
    t:=a[k];a[k]:=a[m];
    i:=m;j:=n;
    while i<>j do
      BEGIN
        while (i<j)and(a[j]>=t)do dec(j);
        if i<j then
        begin
        a:=a[j];inc(i);
        while (a<=t)and(i<j) do inc(i);
        if i<j then begin a[j]:=a;dec(j) end
        end
      END;
    a:=t;
    slipt:=i;
    end;
  BEGIN
    if n>m then begin
    i:=slipt(a,m,n);
    qsort(a,m,i-1);
    qsort(a,i+1,n)
    end
  END;
这是快速排序，时间复杂度为O(nlogn)!与9楼一样

[ 此贴被sunlight在2005-11-16 09:26重新编辑 ]

我的眼球^^^^^^^^^^^^^^^^^^^^

我喜欢用BubbleSort
for i:=1 to n do
for j:=i+1 to n-1 do
  begin t:=a; a:=a[j]; a[j]:=t; end;

真傻！还用Huffmann树
很显然，每次合并两个结点以后，得到的大小是严格递增的，于是我们可以维护两个表，一个是原数字A，一个是新加入的数字B。这样，每次就一定是在A和B的头部取数，在A和B的尾部删除。这样，时间复杂度就降到了O(n)。因为a <= 20000，所以排序也可以用o(20000)的方法来实现，整体时间复杂度为O(n)。
多好的算法！
线性的！

example 中 QSORT 是快排

去年的2题仿佛快排也会超时几个测试点,据说那题用堆排不错

晕，楼上的程序......

program qs(input,output);
type
  list=array[1..8] of integer;
var
  a:list;i:integer;
function partition(p,r:integer;var l:list):integer;
  var
    pivot,i,j,zhong:integer;
  begin
    pivot:=5;
    i:=p-1;
    j:=r+1;
    {while do
    begin   }
      repeat
        dec(j);
      until l[j]<=pivot;
      repeat
        inc(i);
      until l>=pivot;
      if i<j
        then begin
        zhong:=l;
        l:=l[j];
        l[j]:=zhong;
          end
        else if j<>r
        then partition:=j
        else partition:=j-1;
    { end;}
  end;
procedure sort(p,r:integer;var l:list);
  var
    q:integer;
  begin
    if p=r
    then exit
    else begin
      q:=partition(p,r,l);
      sort(p,q,l);
      sort(q+1,r,l);
        end;
  end;
begin
  a[1]:=5;a[2]:=3;a[3]:=2;a[4]:=6;a[5]:=4;a[6]:=1;a[7]:=3;a[8]:=7;
  sort(1,8,a);
  for i:=1 to 8 do
    write(a,' ');
  readln;
end.

我这个程序真么是错的哦，哪个帮我找下原因嘛！！谢谢牛兄！！

请问是EXAMPLE的哪个程序里面有快排哦？？