解决方案 »

  1.   

    还在坚守DELPHI 值得赞美,
      

  2.   

    理论上讲,
    快速排序和希尔排序的速度是很快的,
    但在使用byte数组测试时,发现当数组元素的个数大于等于一千万时,这两种排序速度会很慢,有时报stack over flow , 
    而归并排序和堆排序不存在此问题。
      

  3.   

    快速排序是递归调用,如果层次太深那么就会stack over flow,当然这个跟程序设置stack大小有关系。
    100w的快速排序这么慢不科学。
    另外我想说的是快速排序的i:=L;并不是最好的选择。
    最后我想说的是LZ的实验只做了10000以上,你可以考虑做<20的排序,但是每种做10000次算算总时间,你会发现其他的现象。或许你就能对算法进行优化了。
      

  4.   


    是的,快速排序使用了递归,当元素数量较多时,需要计算机的性能来配合。
    测试发现,2G内存的机器,当排序元素个数<=10万时,其性能与希尔排序、归并排序、堆排序差不多,
    当排序元素个数>=100万时,性能是希尔排序、归并排序、堆排序的四十分之一
      

  5.   

    快速排序由 C. A. R. Hoare(东尼霍尔,Charles Antony Richard Hoare)在1960年提出,之后又有许多人做了进一步的优化。如果你对快速排序感兴趣可以去看看东尼霍尔1962年在Computer Journal发表的论文“Quicksort”以及《算法导论》的第七章。快速排序算法仅仅是东尼霍尔在计算机领域才能的第一次显露,后来他受到了老板的赏识和重用,公司希望他为新机器设计一个新的高级语言。你要知道当时还没有PASCAL或者C语言这些高级的东东。后来东尼霍尔参加了由Edsger Wybe Dijkstra(1972年图灵奖得主,这个大神我们后面还会遇到的到时候再细聊)举办的“ALGOL 60”培训班,他觉得自己与其没有把握去设计一个新的语言,还不如对现有的“ALGOL 60”进行改进,使之能在公司的新机器上使用。于是他便设计了“ALGOL 60”的一个子集版本。这个版本在执行效率和可靠性上都在当时“ALGOL 60”的各种版本中首屈一指,因此东尼霍尔受到了国际学术界的重视。后来他在“ALGOL X”的设计中还发明了大家熟知的“case”语句,后来也被各种高级语言广泛采用,比如PASCAL、C、Java语言等等。当然,东尼霍尔在计算机领域的贡献还有很多很多,他在1980年获得了图灵奖。
      

  6.   

    希尔排序是D.L.Shell于1959年提出来的一种排序算法,在这之前排序算法的时间复杂度基本都是O(n2)的,希尔排序算法是突破这个时间复杂度的第一批算法之一。
      

  7.   


    多年没看到妖哥了。想想离开bcb这么多年了。
      

  8.   


    快速排序 不应该这么慢吧?!
    据说它遇到 接近已经排序的数据 时,才特别慢。你的测试数据是顺序的吗?同意,快速排序对很顺的数据排序比较慢,所以才说他的i的选择并不好。可以改进避免这种情况。为避免这种情况,
    我建议为 快速排序算法 增加一个预处理:随机打乱(按洗牌算法)
    加了这样预处理后,开销仍然是n*ln(n)
      

  9.   


    快速排序 不应该这么慢吧?!
    据说它遇到 接近已经排序的数据 时,才特别慢。你的测试数据是顺序的吗?同意,快速排序对很顺的数据排序比较慢,所以才说他的i的选择并不好。可以改进避免这种情况。为避免这种情况,
    我建议为 快速排序算法 增加一个预处理:随机打乱(按洗牌算法)
    加了这样预处理后,开销仍然是n*ln(n)没有必要这么麻烦,你这还是会导致算法变慢。
      

  10.   

    拿各种数据测试快速排序时,发现随机的数据反而是最慢的?
    在虚拟机:
    array len=999999
    顺序:00:00.093
    顺序,1/5为随机数:00:00.219
    顺序,1/50为随机数:00:00.141
    倒序:00:00.078
    倒序(从32位最大正整数开始):00:00.110
    随机(0-$7fffff):00:00.344
    随机(0-$7fffffff):00:00.296
    array len=999999
    顺序:00:00.125
    顺序,1/5为随机数:00:00.218
    顺序,1/50为随机数:00:00.172
    倒序:00:00.094
    倒序(从32位最大正整数开始):00:00.093
    随机(0-$7fffff):00:00.282
    随机(0-$7fffffff):00:00.312在宿主机:
    array len=999999
    顺序:00:00.079
    顺序,1/5为随机数:00:00.207
    顺序,1/50为随机数:00:00.145
    倒序:00:00.083
    倒序(从32位最大正整数开始):00:00.104
    随机(0-$7fffff):00:00.311
    随机(0-$7fffffff):00:00.283
    array len=999999
    顺序:00:00.079
    顺序,1/5为随机数:00:00.198
    顺序,1/50为随机数:00:00.151
    倒序:00:00.085
    倒序(从32位最大正整数开始):00:00.088
    随机(0-$7fffff):00:00.299
    随机(0-$7fffffff):00:00.303
      

  11.   

    测试结果有点意思:
    csdn就是楼主的快速排序算法
    csdnrnd是预先多进行一轮打乱
    my是我网上找的一个改进的快速排序算法——不怕数据是已排序的,而且堆栈开销也低很多,但是完全随机的数据,它略慢array len=100000
    顺序:
    csdn   :00:03.664
    csdnRnd:00:00.010
    my     :00:00.007
    顺序,1/5为随机数
    csdn   :00:00.008
    csdnRnd:00:00.010
    my     :00:00.016
    顺序,1/50为随机数
    csdn   :00:00.013
    csdnRnd:00:00.009
    my     :00:00.017
    倒序
    csdn   :00:03.703
    csdnRnd:00:00.012
    my     :00:00.009
    倒序(从32位最大正整数开始):
    csdn   :00:03.680
    csdnRnd:00:00.009
    my     :00:00.008
    随机(0-$7fffff)
    csdn   :00:00.009
    my     :00:00.026
    随机(0-$7fffffff)
    csdn   :00:00.009
    my     :00:00.026
    array len=100000
    顺序:
    csdn   :00:03.660
    csdnRnd:00:00.009
    my     :00:00.010
    顺序,1/5为随机数
    csdn   :00:00.011
    csdnRnd:00:00.010
    my     :00:00.019
    顺序,1/50为随机数
    csdn   :00:00.014
    csdnRnd:00:00.011
    my     :00:00.015
    倒序
    csdn   :00:03.615
    csdnRnd:00:00.010
    my     :00:00.007
    倒序(从32位最大正整数开始):
    csdn   :00:03.622
    csdnRnd:00:00.011
    my     :00:00.008
    随机(0-$7fffff)
    csdn   :00:00.010
    csdnRnd:00:00.010
    my     :00:00.024
    随机(0-$7fffffff)
    csdn   :00:00.009
    csdnRnd:00:00.010
    my     :00:00.024
    【网上找的一个改进的快速排序算法】
    unit UnitQuickSort;interfacetype
      TfunCompare=function (data:pointer;a,b:Integer):Integer;
      TfunExchange=procedure (data:pointer;a,b:Integer);procedure QuickSort(data:pointer; L, R: Integer; SCompare: TfunCompare;ExchangeItems: TfunExchange);implementationprocedure QuickSort(data:pointer; L, R: Integer; SCompare: TfunCompare;ExchangeItems: TfunExchange);
    var
      I, J, P: Integer;
    begin
      repeat
        I := L;
        J := R;
        P := (L + R) shr 1;
        repeat
          while SCompare(data,I, P) < 0 do Inc(I);
          while SCompare(data,J, P) > 0 do Dec(J);
          if I <= J then
          begin
            ExchangeItems(data,I, J);
            if P = I then
              P := J
            else if P = J then
              P := I;
            Inc(I);
            Dec(J);
          end;
        until I > J;
        if L < J then QuickSort(data, L, J, SCompare, ExchangeItems);
        L := I;
      until I >= R;
    end;end.
      

  12.   

    补充一个js的,虽然代码是js,但是说明比较详细:
    http://www.codeceo.com/article/javascript-9-sort-algorithms.html
      

  13.   

    弱弱的问一下,现在Delphi在那些领域使用。自己没有再使用Delphi已经6-7年了
      

  14.   


    在移动开发方便、稳定之前,Delphi擅长的领域 并没有变化
      

  15.   

    说实话,像楼主代码里的不定长数组这类东西,我都不太会。。现在毕竟大部分代码还是用C++写。。
    只有自己写一些GUI程序会用delphi,因为实在不通MFC等那些玩意。。
      

  16.   


    在移动开发方便、稳定之前,Delphi擅长的领域 并没有变化
    还好 :-) 之前主要是用Delphi做C/S架构的ERP系统什么的,当时觉着这东西简直好用的神了
      

  17.   


    在移动开发方便、稳定之前,Delphi擅长的领域 并没有变化
    还好 :-) 之前主要是用Delphi做C/S架构的ERP系统什么的,当时觉着这东西简直好用的神了从方便开发者的角度看,delphi是空前绝后的。
    所以用过delphi,再用别的语言工具,都觉得是回到原始社会了
      

  18.   

    支持一下,第一次看到用delphi研究算法的,嘿嘿。只要看到算法的东西都是c代码。
      

  19.   

    楼主的快速排序代码不对,这是Delphi自带的快速排序,速度遥遥领先其他所有算法,
    而且即使1千万个数据也没有栈溢出
    type
    TIntArray=array of integer;procedure QuickSort0(var A: TIntArray; iLo, iHi: Integer);
      var
     Lo, Hi, Mid, T: Integer;
      begin
     Lo := iLo;
     Hi := iHi;
     Mid := A[(Lo + Hi) div 2];
     repeat
    while A[Lo] < Mid do Inc(Lo);
    while A[Hi] > Mid do Dec(Hi);
    if Lo <= Hi then
    begin
      T := A[Lo];
      A[Lo] := A[Hi];
      A[Hi] := T;
      Inc(Lo);
      Dec(Hi);
    end;
     until Lo > Hi;
     if Hi > iLo then QuickSort0(A, iLo, Hi);
     if Lo < iHi then QuickSort0(A, Lo, iHi);
      end;procedure QuickSort(var x:TIntArray);
    begin
    QuickSort0(x,Low(x),High(x));
    end;