排序算法总结.doc

排序操作总结program Sort_Ascending;$R+const maxn=100; c1=0; cd=9;type arr=array0.maxnof integer; recnode=record key:string; next:integer; end; listtp=array1.maxnof recnode; arrtp=arrayc1.cdof integer;var s:arr; n,d:integer;procedure init;var i:integer;begin write(n=); readln(n); write(Input Num:); for i:=1 to n do read(si); readln;end;procedure print(s:arr);var i:integer;begin for 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;begin for i:=2 to n do if sisi-1 then begin s0:=si; j:=i-1; while s0n; end; procedure ShellInsert(var s:arr; dk:integer); var i,j:integer; begin for i:=dk+1 to n do if (si0)and(s0sj+1 then begin temp:=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; begin i:=h; j:=t; p:=sh; x:=sh; while ij do begin while (i=x)do dec(j); si:=sj; while (ij)and(si=x)do inc(i); sj:=si; end; si:=p; if ht then begin qsort(s,h,i-1); qsort(s,i+1,t); end; end;begin qsort(s,1,n); write(QuickSort: ); print(s);end;procedure SelectSort(s:arr);Time:O(n2) Room:O(1) -Unstable sorting method-var i,j,k,temp:integer;begin for i:=1 to n-1 do begin k:=i; for j:=i+1 to n do if sjsk then k:=j; if ik then begin temp:=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; begin i:=h; j:=2*i; x:=sh; while j=t do begin if (jt)and(sj=sj then break; si:=sj; i:=j; j:=2*i; end; si:=x; end; procedure hsort(var s:arr); var i:integer; begin for i:=n div 2 downto 1 do sift(s,i,n); for i:=n downto 2 do begin s0:=s1; s1:=si; si:=s0; sift(s,1,i-1); end; end;begin hsort(s); write(HeapSort: ); print(s);end;procedure MergeSort(s:arr);Time: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; begin t:=p; i:=p; j:=q+1; while t=r do begin if (ir)or(si=sj) then begin tempt:=si; inc(i); end else begin tempt:=sj; inc(j); end; inc(t); end; for i:=p to r do si:=tempi; end; procedure msort(var s:arr; p,r:integer); var q:integer; begin if pr then begin q:=(p+r-1) div 2; msort(s,p,q); msort(s,q+1,r); merge(s,p,q,r); end; end;begin msort(s,1,n); write(MergeSort: ); print(s);end;procedure RadixSort(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 for j:=c1 to cd do fj:=0; while p0 do begin val(rp.keyi,j,code); if fj=0 then fj:=p else rej.next:=p; ej:=p; p:=rp.next; end; end; procedure collect(var r:listtp; i:integer; f,e:arrtp; var p:integer); var j,t:integer; begin j:=c1; while fj=0 do j:=succ(j); p:=fj; t:=ej; while jcd do begin j:=succ(j); while (jcd)and(fj=0)do j:=succ(j); if fj0 then begin rt.next:=fj; t:=ej; end; end; rt.next:=0; end; procedure rsprint(p:integer); var i,j:integer; begin while p0 do begin j:=1; while rp.keyj=0 do begin delete(rp.key,1,1); inc(j); end; write(rp.key, ); p:=rp.next; end; writeln; end;begin write(RadixSort-d=); readln(d); for i:=1 to n do begin str(si,ri.key); ri.next:=i+1; if length(ri.key)d then for 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 do begin distribute(r,p,i,f,e); collect(r,i,f,e,