常用算法表概要

1、常用算法表模塊一排序1、冒泡排序0(nT)小規(guī)模，短代碼procedure bsort(var arr:arrtype;le n:l ongin t);vari,j,t:lo ngi nt;beg infor i:=1 to len-1 dofor j:=i+1 to len doif arri>arrj then begin t:=arri; arri:=arrj; arrj:=t; end;end;2、 插入排序0(nlgn)中規(guī)模，中代碼 procedure isort(var arr:arrtype;le n:lo ngin t);vari,key,f,r,q:l ongint;

2、beg infor i:=2 to len do beg inkey:=arri;f:=1;r:=i;while f<r do beg in q:=(f+r) div 2; if arrq<key the n f:=q+1 else r:=q; end;move(arrf,arrf+1,(i-f)*4);arrf:=key;end;end:3、快速排序O(nlgn)大規(guī)模，中長代碼procedure quick_sort(var a:arrtype;f,r:l ongin t); varx,i,j,t,ra nd:l ongint;beg inif f<r the n beg

3、 in ran d:=ra ndom(r-f)+f; t:=ar; ar:=ara nd; ara nd:=t; x:=ar;i:=f-1;j:=r+1;while true do begi nrepeat dec(j) un til aj<=x; repeat in c(i) un til ai>=x; if i<j the n beg int:=aj;aj:=ai;ai:=t;endelse break; end; quick_sort(a,f,j); quick_sort(a,i,r); end;end;4、計數(shù)排序0(n)超大規(guī)模，單純排序，單數(shù)據(jù)小，短代碼 proc

4、edure coun t_sort(var a:arrtype);varmin, max,i,r:lo ngi nt;h:array-5000000.5000000of Ion gi nt;beg inmi n:=maxl ongin t; max:=-maxl ongint;for i:=1 to a0 do beg inin c(hai);if ai>max the n max:=t;if ai<min then min:=t;end;r:=0;for i:=min to max do if hi>0 the nfor j:=1 to hi do beg in in c(

5、r); ar:=i;end;end;5、基數(shù)排序0(n*k)超大規(guī)模，單純排序，單數(shù)據(jù)大，長代碼(負數(shù)處理要另外寫代碼)procedure radix_sort(var a:arrtype;le n:i nteger); vari,t,te n,j,k,rear:l ongint; r:array0.9,0.1of longint;beg inten :=1;for i:=1 to len do beg in fillchar(q,sizeof(q),0); fillchar(r,sizeof(r),0); rear:=0;for j:=1 to a0 do beg in t:=(ajdiv

6、ten) mod 10; in c(rear); if rt,0=0the n rt,0:=rear else q1,rt,1:=j;rt,1:=rear; q0,rear:=aj; end;k:=0;for j:=0 to 9 do beg in t:=rj,0;while t<>0 do beg in in c(k);ak:=q0,t; t:=q1,t; end;end; ten: =te n*10; end;end;模塊二樹,插入1、堆的維護(heap_fix) ，元素改變(heap_change)，刪除(heap_killmax)(heap_insert)，時間復(fù)雜度均為O

7、(lgn)procedure heap_fix(var a:heaptype;i:l ongin t); varl,r,largest,t:l ongint;beg inl:=i*2;r:=l+1;if (l<=a0)a nd(al>ai)the n largest:=l; else largest:=i;if (r<=a0)a nd(ar>alargest)the n largest:=r;if largest<>i the n begi nt:=ai;ai:=alargest; alargest:=t;heap_fix(a,largest); end;e

8、nd;procedure heap_cha nge(var a:heaptype;x,key:l ongin t); vart:lo ngint;beg inif key<ax the n begi n ax:=key; heap_fix(a,x); end else beg in ax:=key; while (x>1)a nd(Ax div 2<ax) do begin t:=ax;ax:=ax div 2; ax div 2:=t; x:=x div 2; end;end;end;fun cti on heap_killmax(var a:heaptype):lo ng

9、int; beg inheap_killmax:=a1; a1:=aa0;dec(a0); heap_fix(a,1);end;procedure heap_i nsert(var a:heaptype;key:lo ngi nt); beg inin c(a0);aa0:=-maxl ongint; heap_cha nge(a,a0,key);end;2、堆的建立(heap_build) ，堆的排序(heap_sort)，時間復(fù)雜度均為 O(nlgn)procedure heap_build(var a:heaptype);vari:i nteger;beg infor i:=a0 div 2 downto 1 do heap_fix(a,i);end;procedure heap_sort(var a:heaptype);vari,t,le n:lo n