排序算法总结.doc

1、排序操作总结第 1 页 共 7 页program Sort_Ascending;$R+const maxn=100;c1=0; cd=9;type arr=array0.maxnof integer;recnode=recordkey:string;next:integer;end;listtp=array1.maxnof recnode;arrtp=arrayc1.cdof integer;var s:arr;n,d:integer;procedure init;var i:integer;beginwrite(n=); readln(n);write(Input Num:); for i:

2、=1 to n do read(si);readln;end;procedure print(s:arr);var i:integer;beginfor i:=1 to n do write(si, );writeln;end;procedure InsertSort(s:arr);Time:O(n2) Room:O(1) -Stable sorting method-var i,j:integer;beginfor i:=2 to n doif sin;end;procedure ShellInsert(var s:arr; dk:integer);var i,j:integer;begin

3、for i:=dk+1 to n doif (si0)and(s0sj+1 thenbegintemp:=sj; sj:=sj+1; sj+1:=temp;flag:=false;end;inc(i);until flag;write(BubbleSort: ); print(s);end;procedure QuickSort(s:arr);Time:O(nlog 2 n) Room:O(log 2 n) -Unstable sorting method-procedure qsort(var s:arr; h,t:integer);var i,j,p,x:integer;begini:=h

4、; j:=t; p:=sh; x:=sh;while i=x)do dec(j);si:=sj;while (ik thenbegintemp:=si; si:=sk; sk:=temp;end;end;write(SelectSort: ); print(s);end;procedure HeapSort(s:arr);Time:O(n log 2 n) Room:O(1) -Unstable sorting method-procedure sift(var s:arr; h,t:integer);var i,j,x:integer;begini:=h; j:=2*i; x:=sh;whi

5、le j=sj then break;si:=sj; i:=j; j:=2*i;end;si:=x;end;procedure hsort(var s:arr);var i:integer;beginfor i:=n div 2 downto 1 do sift(s,i,n);for i:=n downto 2 dobegins0:=s1; s1:=si; si:=s0;sift(s,1,i-1);end;end;beginhsort(s);write(HeapSort: ); print(s);end;排序操作总结第 5 页 共 7 页procedure MergeSort(s:arr);T

6、ime:O(nlog 2 n) Room:O(n) -Stable sorting method-procedure merge(var s:arr; p,q,r:integer);var i,j,t:integer;temp:arr;begint:=p; i:=p; j:=q+1;while tr)or(sir thenbeginq:=(p+r-1) div 2;msort(s,p,q);msort(s,q+1,r);merge(s,p,q,r);end;end;beginmsort(s,1,n);write(MergeSort: ); print(s);end;procedure Radi

7、xSort(s:arr);var r:listtp;f,e:arrtp;i,j,p:integer;procedure distribute(var r:listtp; p,i:integer; var f,e:arrtp);var j,code:integer;begin排序操作总结第 6 页 共 7 页for j:=c1 to cd do fj:=0;while p0 dobeginj:=1;while rp.keyj=0 dobegin delete(rp.key,1,1); inc(j); end;write(rp.key, );p:=rp.next;end;writeln;end;b

8、eginwrite(RadixSort-d=); readln(d);for i:=1 to n dobeginstr(si,ri.key); ri.next:=i+1;排序操作总结第 7 页 共 7 页if length(ri.key)d thenfor j:=1 to d-length(ri.key) do insert(0,ri.key,1);end;rn.next:=0;fillchar(f,sizeof(f),0); fillchar(e,sizeof(e),0);p:=1;for i:=d downto 1 dobegindistribute(r,p,i,f,e);collect(r,i,f,e,p);end;write(RadixSort: ); rsprint(p);end;begininit;InsertSort(s);ShellSort(s);BubbleSort(s);QuickSort(s);SelectSort(s);HeapSort(s);MergeSort(s);RadixSort(s);end.