快速排序由 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年获得了图灵奖。
测试结果有点意思: 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.
楼主的快速排序代码不对,这是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;
快速排序和希尔排序的速度是很快的,
但在使用byte数组测试时,发现当数组元素的个数大于等于一千万时,这两种排序速度会很慢,有时报stack over flow ,
而归并排序和堆排序不存在此问题。
100w的快速排序这么慢不科学。
另外我想说的是快速排序的i:=L;并不是最好的选择。
最后我想说的是LZ的实验只做了10000以上,你可以考虑做<20的排序,但是每种做10000次算算总时间,你会发现其他的现象。或许你就能对算法进行优化了。
是的,快速排序使用了递归,当元素数量较多时,需要计算机的性能来配合。
测试发现,2G内存的机器,当排序元素个数<=10万时,其性能与希尔排序、归并排序、堆排序差不多,
当排序元素个数>=100万时,性能是希尔排序、归并排序、堆排序的四十分之一
多年没看到妖哥了。想想离开bcb这么多年了。
快速排序 不应该这么慢吧?!
据说它遇到 接近已经排序的数据 时,才特别慢。你的测试数据是顺序的吗?同意,快速排序对很顺的数据排序比较慢,所以才说他的i的选择并不好。可以改进避免这种情况。为避免这种情况,
我建议为 快速排序算法 增加一个预处理:随机打乱(按洗牌算法)
加了这样预处理后,开销仍然是n*ln(n)
快速排序 不应该这么慢吧?!
据说它遇到 接近已经排序的数据 时,才特别慢。你的测试数据是顺序的吗?同意,快速排序对很顺的数据排序比较慢,所以才说他的i的选择并不好。可以改进避免这种情况。为避免这种情况,
我建议为 快速排序算法 增加一个预处理:随机打乱(按洗牌算法)
加了这样预处理后,开销仍然是n*ln(n)没有必要这么麻烦,你这还是会导致算法变慢。
在虚拟机:
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
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.
http://www.codeceo.com/article/javascript-9-sort-algorithms.html
在移动开发方便、稳定之前,Delphi擅长的领域 并没有变化
只有自己写一些GUI程序会用delphi,因为实在不通MFC等那些玩意。。
在移动开发方便、稳定之前,Delphi擅长的领域 并没有变化
还好 :-) 之前主要是用Delphi做C/S架构的ERP系统什么的,当时觉着这东西简直好用的神了
在移动开发方便、稳定之前,Delphi擅长的领域 并没有变化
还好 :-) 之前主要是用Delphi做C/S架构的ERP系统什么的,当时觉着这东西简直好用的神了从方便开发者的角度看,delphi是空前绝后的。
所以用过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;