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

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

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

example 中 QSORT 是快排

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

我喜欢用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;

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

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重新编辑 ]