您的位置: 首页  >  IT文章  >  Delphi  >  delphi实现惯用的几种排序算法

delphi实现惯用的几种排序算法

分类: IT文章 • 2024-11-04 18:09:01
delphi实现常用的几种排序算法
1.冒泡排序


procedure BubbleSort(var x:array of integer);

var

  i,j,intTmp:integer;

begin

  for i:=0 to high(x) do

  begin

    for j:=0 to high(x)-1 do

    begin

      if x[j]>x[j+1] then

      begin

        intTmp:=x[j];

        x[j]:=x[j+1];

        x[j+1]:=intTmp;

      end;

    end;

  end;

end;



2.选择排序


procedure SelectSort(var x:array of integer);

var

  i,j,k,intTmp:integer;

begin

  for i:=0 to high(x)-1 do

  begin

    intTmp:=x[i];

    k:=i;

    for j:=i+1 to high(x) do

    begin

      if intTmp>x[j] then

      begin

        k:=j;

        intTmp:=x[k];

      end;

    end;

    if k<>i then

    begin

      x[k]:=x[i];

      x[i]:=intTmp;

    end;

  end;

end;



3.插入排序


procedure InsertSort(var x:array of integer);

var

  i,j,intTmp:integer;

begin

  for i:=1 to high(x) do

  begin

    for j:=i downto 1 do

    begin

      if x[j-1]>x[j] then

      begin

        intTmp:=x[j-1];

        x[j-1]:=x[j];

        x[j]:=intTmp;

      end;

    end;

  end;

end;



4.希尔排序


procedure ShellSort(var x:array of integer);

var

  h,i,j,intTmp:integer;

begin

  h:=high(x) div 2;

  while h>0 do

  begin

    for i:=h to high(x) do

    begin

      j:=i;

      while (j>=h) and (x[j-h]>x[j]) do

      begin

        intTmp:=x[j-h];

        x[j-h]:=x[j];

        x[j]:=intTmp;

        j:=j-h;

      end;

    end;

    h:=h div 2;

  end;

end;



5.快速排序


procedure QuickSort(var x:array of integer; L,R:integer);

var

  i,j,intTmp:integer;

begin

  if L<R then

  begin

    i:=L;

    j:=R;

    intTmp:=x[i];

    while i<j do

    begin

      while (i<j) and (x[j]>=intTmp) do

      begin

        j:=j-1;

      end;

      if i<j then x[i]:=x[j];

      while (i<j) and (x[i]<=intTmp) do

      begin

        i:=i+1;

      end;

      if i<j then x[j]:=x[i];

    end;

    x[i]:=intTmp;

    QuickSort(x,L,i-1);

    QuickSort(x,i+1,R);

  end;

end;



6.归并排序


procedure Merge(var x,y:array of integer; L,M,R:integer);

var

  i,j:integer;

begin

  i:=L;

  j:=M+1;

  while (L<=M) and (j<=R) do

  begin

    if x[L]> x[j] then

    begin

      y[i]:=x[j];

      j:=j+1;

    end

    else

    begin

      y[i]:=x[L];

      L:=L+1;

    end;

    i:=i+1;

  end;

  while L<=M do

  begin

    y[i]:=x[L];

    i:=i+1;

    L:=L+1;

  end;

  while j<=R do

  begin

    y[i]:=x[j];

    i:=i+1;

    j:=j+1;

  end;

end;


procedure MergeSort(var x, y:TArrInt);

var

  intLength,intLen,intLen_m,i:integer;

  tmp:TArrInt;

begin

  intLength:=high(x)+1;

  intLen:=1;


  while intLen<intLength do

  begin

    intLen_m:=intLen;

    intLen:=intLen*2;

    i:=0;

    while i+intLen<intLength do

    begin

      Merge(x,y,i,i+intLen_m-1,i+intLen-1);

      i:=i+intLen;

    end;

    if i+intLen_m<intLength then

    begin

      Merge(x,y,i,i+intLen_m-1,intLength-1);

    end;


    tmp:=x;

    x:=y;

    y:=tmp;

  end;

end;



7.堆排序


procedure HeapAdjust(var x:array of integer; i,intLen:integer);

var

  intTmp,intChild:integer;

begin

  intTmp:=x[i];

  intChild:=2*i+1;

  while intChild<intLen do

  begin

    if (intChild+1<intLen) and (x[intChild]<x[intChild+1]) then

    begin

      intChild:=intChild+1;

    end;

    if x[i]<x[intChild] then

    begin

      x[i]:=x[intChild];

      i:=intChild;

      intChild:=2*i+1;

    end

    else

    begin

      break;

    end;

    x[i]:=intTmp;

  end;

end;


procedure BuildHeap(var x:array of integer);

var

  i:integer;

begin

  for i:=high(x) div 2 downto 0 do

  begin

    HeapAdjust(x,i,High(x)+1);

  end;

end;


procedure HeapSort(var x:array of integer);

var

  i,intTmp:integer;

begin

  BuildHeap(x);

  for i:=high(x) downto 0 do

  begin

    intTmp:=x[i];

    x[i]:=x[0];

    x[0]:=intTmp;

    HeapAdjust(x,0,i);

  end;

end;

------解决思路----------------------
已收藏，谢谢！
------解决思路----------------------
还在坚守DELPHI 值得赞美，
------解决思路----------------------
总结与实验，非常清晰。顶！
------解决思路----------------------
支持楼主总结
------解决思路----------------------
快速排序是递归调用，如果层次太深那么就会stack over flow，当然这个跟程序设置stack大小有关系。
100w的快速排序这么慢不科学。
另外我想说的是快速排序的i:=L;并不是最好的选择。
最后我想说的是LZ的实验只做了10000以上，你可以考虑做<20的排序，但是每种做10000次算算总时间，你会发现其他的现象。或许你就能对算法进行优化了。


------解决思路----------------------
好有耐心的啊、delphi实现惯用的几种排序算法
------解决思路----------------------
谢谢楼主分享
------解决思路----------------------
楼主总算走上正途了
------解决思路----------------------
delphi实现惯用的几种排序算法
------解决思路----------------------
引用:
性能测试对比
单位：毫秒
delphi实现惯用的几种排序算法


快速排序 不应该这么慢吧？！
据说它遇到 接近已经排序的数据 时，才特别慢。。。。你的测试数据是顺序的吗？
------解决思路----------------------
引用:
Quote: 引用:

性能测试对比
单位：毫秒
delphi实现惯用的几种排序算法


快速排序 不应该这么慢吧？！
据说它遇到 接近已经排序的数据 时，才特别慢。。。。你的测试数据是顺序的吗？


同意，快速排序对很顺的数据排序比较慢，所以才说他的i的选择并不好。可以改进避免这种情况。
------解决思路----------------------
引用:
楼主总算走上正途了


多年没看到妖哥了。想想离开bcb这么多年了。
------解决思路----------------------
引用:
Quote: 引用:

Quote: 引用:

性能测试对比
单位：毫秒
delphi实现惯用的几种排序算法


快速排序 不应该这么慢吧？！
据说它遇到 接近已经排序的数据 时，才特别慢。。。。你的测试数据是顺序的吗？


同意，快速排序对很顺的数据排序比较慢，所以才说他的i的选择并不好。可以改进避免这种情况。


为避免这种情况，
我建议为 快速排序算法 增加一个预处理：随机打乱（按洗牌算法）
加了这样预处理后，开销仍然是n*ln(n)
------解决思路----------------------
留个丫子，学习了
------解决思路----------------------
引用:
Quote: 引用:

Quote: 引用:

Quote: 引用:

性能测试对比
单位：毫秒
delphi实现惯用的几种排序算法


快速排序 不应该这么慢吧？！
据说它遇到 接近已经排序的数据 时，才特别慢。。。。你的测试数据是顺序的吗？


同意，快速排序对很顺的数据排序比较慢，所以才说他的i的选择并不好。可以改进避免这种情况。


为避免这种情况，
我建议为 快速排序算法 增加一个预处理：随机打乱（按洗牌算法）
加了这样预处理后，开销仍然是n*ln(n)


没有必要这么麻烦，你这还是会导致算法变慢。
------解决思路----------------------
希尔排序为什么没有继续下去？
------解决思路----------------------
learning
------解决思路----------------------
拿各种数据测试快速排序时，发现随机的数据反而是最慢的？
在虚拟机：
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
------解决思路----------------------
很好 delphi实现惯用的几种排序算法
------解决思路----------------------
好帖，整理的非常清晰。
------解决思路----------------------
不错，收藏下delphi实现惯用的几种排序算法
------解决思路----------------------
delphi 现在还有人用啊
------解决思路----------------------
测试结果有点意思：
****就是楼主的快速排序算法
****rnd是预先多进行一轮打乱
my是我网上找的一个改进的快速排序算法——不怕数据是已排序的，而且堆栈开销也低很多，但是完全随机的数据，它略慢

array len=100000
顺序：
****   :00:03.664
****Rnd:00:00.010
my     :00:00.007
顺序，1/5为随机数
****   :00:00.008
****Rnd:00:00.010
my     :00:00.016
顺序，1/50为随机数
****   :00:00.013
****Rnd:00:00.009
my     :00:00.017
倒序
****   :00:03.703
****Rnd:00:00.012
my     :00:00.009
倒序（从32位最大正整数开始）：
****   :00:03.680
****Rnd:00:00.009
my     :00:00.008
随机（0-$7fffff）
****   :00:00.009
my     :00:00.026
随机（0-$7fffffff）
****   :00:00.009
my     :00:00.026




array len=100000
顺序：
****   :00:03.660
****Rnd:00:00.009
my     :00:00.010
顺序，1/5为随机数
****   :00:00.011
****Rnd:00:00.010
my     :00:00.019
顺序，1/50为随机数
****   :00:00.014
****Rnd:00:00.011
my     :00:00.015
倒序
****   :00:03.615
****Rnd:00:00.010
my     :00:00.007
倒序（从32位最大正整数开始）：
****   :00:03.622
****Rnd:00:00.011
my     :00:00.008
随机（0-$7fffff）
****   :00:00.010
****Rnd:00:00.010
my     :00:00.024
随机（0-$7fffffff）
****   :00:00.009
****Rnd:00:00.010
my     :00:00.024


【网上找的一个改进的快速排序算法】


unit UnitQuickSort;


interface


type

  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);


implementation


procedure 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.

------解决思路----------------------
好帖，整理的非常清晰。不错，收藏下delphi实现惯用的几种排序算法
------解决思路----------------------
顶。收藏学习下
------解决思路----------------------
Delphi的帖子，得顶一下
------解决思路----------------------
delphi实现惯用的几种排序算法
------解决思路----------------------
补充一个js的，虽然代码是js，但是说明比较详细：
http://www.codeceo.com/article/javascript-9-sort-algorithms.html
------解决思路----------------------
弱弱的问一下，现在Delphi在那些领域使用。自己没有再使用Delphi已经6-7年了。。。
------解决思路----------------------
引用:
弱弱的问一下，现在Delphi在那些领域使用。自己没有再使用Delphi已经6-7年了。。。


在移动开发方便、稳定之前，Delphi擅长的领域 并没有变化
------解决思路----------------------
有鸟用？？？？？？？？？？？？？
------解决思路----------------------
说实话，像楼主代码里的不定长数组这类东西，我都不太会。。现在毕竟大部分代码还是用C++写。。
只有自己写一些GUI程序会用delphi，因为实在不通MFC等那些玩意。。
------解决思路----------------------
引用:
Quote: 引用:

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


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

还好 :-) 之前主要是用Delphi做C/S架构的ERP系统什么的，当时觉着这东西简直好用的神了delphi实现惯用的几种排序算法
------解决思路----------------------
引用:
Quote: 引用:

Quote: 引用:

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


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

还好 :-) 之前主要是用Delphi做C/S架构的ERP系统什么的，当时觉着这东西简直好用的神了delphi实现惯用的几种排序算法


从方便开发者的角度看，delphi是空前绝后的。。。。
所以用过delphi，再用别的语言工具，都觉得是回到原始社会了
------解决思路----------------------
随机化快排会好些.
------解决思路----------------------
mark之，有用！
------解决思路----------------------
支持一下，第一次看到用delphi研究算法的，嘿嘿。只要看到算法的东西都是c代码。
------解决思路----------------------
楼主的快速排序代码不对,这是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;

相关推荐