切换到宽版
  • 56721阅读
  • 111回复

排序 [复制链接]

上一主题 下一主题
离线qswb
只看该作者 20 发表于: 2006-02-12
归并排序

归并就是将多个有序的数列合成一个有序的数列。将两个有序序列合并为一个有序序列叫二路归并(merge).归并排序就是n长度为1的子序列,两两归并最后变为有序的序列。

1.二路归并

例1:将有序表L1=(1,5,7),L2=(2,3,4,6,8,9,10)合并一个有序表 L.

program gb;

const m=3;n=7;

type arrl1=array[1..m] of integer;

arrl2=array[1..n] of integer;

arrl=array[1..m+n] of integer;

var a:arrl1;

b:arrl2;

c:arrl;

i,j,k,r:integer;

begin

write('Enter l1(sorted):');

for i:=1 to m do read(a);

write('Enter l2(sorted):');

for i:=1 to n do read(b);

i:=1;j:=1;k:=0;

while (i<=m) and (j<=n) do

begin

k:=k+1;

if a<=b[j] then begin c[k]:=a;i:=i+1; end

          else begin c[k]:=b[j];j:=j+1;end;

end;

if i<=m then for r:=i to m do c[m+r]:=a[r];

if j<=n then for r:=j to n do c[n+r]:=b[r];

writeln('Output data:');

for i:=1 to m+n do write(c:5);

writeln;

end.

2.归并排序

program gbpx;
const maxn=7;
type arr=array[1..maxn] of integer;
var a,b,c:arr;
  i:integer;
procedure merge(r:arr;l,m,n:integer;var r2:arr);
var i,j,k,p:integer;
begin
i:=l;j:=m+1;k:=l-1;
while (i<=m)and (j<=n) do
begin
  k:=k+1;
  if r<=r[j] then begin r2[k]:=r;i:=i+1 end
          else begin r2[k]:=r[j];j:=j+1 end
end;
if i<=m then
for p:=i to m do begin k:=k+1;r2[k]:=r[p] end;
if j<=n then
for p:=j to n do begin k:=k+1;r2[k]:=r[p] end;
end;
procedure mergesort( var r,r1:arr;s,t:integer);
var k:integer; c:arr;
begin
if s=t then r1[s]:=r[s] else
  begin
  k:=(s+t) div 2;
  mergesort(r,c,s,k);
  mergesort(r,c,k+1,t);
  merge(c,s,k,t,r1)
  end;
end;
begin
write('Enter data:');
for i:= 1 to maxn do
read(a);
mergesort(a,b,1,maxn);
for i:=1 to maxn do
write(b:9);
writeln;
end.
离线qswb
只看该作者 21 发表于: 2006-02-12
各种排序算法的比较

1.稳定性比较

插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的

选择排序、希尔排序、快速排序、堆排序是不稳定的

2.时间复杂性比较

插入排序、冒泡排序、选择排序的时间复杂性为O(n2)

其它非线形排序的时间复杂性为O(nlog2n)

线形排序的时间复杂性为O(n);

3.辅助空间的比较

线形排序、二路归并排序的辅助空间为O(n),其它排序的辅助空间为O(1);

4.其它比较

插入、冒泡排序的速度较慢,但参加排序的序列局部或整体有序时,这种排序能达到较快的速度。

反而在这种情况下,快速排序反而慢了。

当n较小时,对稳定性不作要求时宜用选择排序,对稳定性有要求时宜用插入或冒泡排序。

若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。

当n较大时,关键字元素比较随机,对稳定性没要求宜用快速排序。

当n较大时,关键字元素可能出现本身是有序的,对稳定性有要求时,空间允许的情况下。

宜用归并排序。

当n较大时,关键字元素可能出现本身是有序的,对稳定性没有要求时宜用堆排序。
离线johnson
只看该作者 22 发表于: 2006-08-16
谢谢,我拷了。
离线putaoshangu
只看该作者 23 发表于: 2006-09-20
高手!
离线流星揽月
只看该作者 24 发表于: 2006-10-19
很有用
离线流星揽月
只看该作者 25 发表于: 2006-10-19
牛啊啊
离线gabriel
只看该作者 26 发表于: 2006-10-21
我天哪~~我的耐心还是不够
离线angel_zxl
只看该作者 27 发表于: 2006-10-23
谢谢!
离线tstone
只看该作者 28 发表于: 2006-10-23
狂晕~~~
这么专业~~~
离线dorra
只看该作者 29 发表于: 2006-10-28
thanks
快速回复
限100 字节
 
上一个 下一个