《pascal语言多种排序算法源程序》由会员分享,可在线阅读,更多相关《pascal语言多种排序算法源程序(3页珍藏版)》请在金锄头文库上搜索。
1、PASCAL语言多种排序算法源程序 1.快速排序:procedure qsort(l,r:integer);var i,j,mid:integer;begini:=l;j:=r; mid:=a(l+r) div 2; 将当前序列在中间位置的数定义为中间数repeatwhile aimid do dec(j);在右半部分寻找比中间数小的数if ij;if lj then qsort(l,j); 若未到两个数的边界,则递归搜索左右区间if ir then qsort(i,r);end;sort 2.插入排序:思路:当前a1.ai-1已排好序了,现要插入ai使a1.ai有序。procedure in
2、sert_sort;var i,j:integer;beginfor i:=2 to n do begina0:=ai;j:=i-1;while a0aj then swap(ai,aj); end; 4. 冒泡排序procedure bubble_sort;var i,j,k:integer;beginfor i:=1 to n-1 dofor j:=n downto i+1 doif ajaj-1 then swap( aj,aj-1); 每次比较相邻元素的关系end; 5.堆排序:procedure sift(i,m:integer);调整以i为根的子树成为堆,m为结点总数var k:i
3、nteger;begina0:=ai; k:=2*i;在完全二叉树中结点i的左孩子为2*i,右孩子为2*i+1while k=m do beginif (km) and (akak+1) then inc(k);找出ak与ak+1中较大值if a0ak then begin ai:=ak;i:=k;k:=2*i; endelse k:=m+1;end;ai:=a0; 将根放在合适的位置end;procedure heapsort;varj:integer;beginfor j:=n div 2 downto 1 do sift(j,n);for j:=n downto 2 do beginsw
4、ap(a1,aj);sift(1,j-1);end;end; 6. 归并排序a为序列表,tmp为辅助数组procedure merge(var a:listtype; p,q,r:integer);将已排序好的子序列ap.q与aq+1.r合并为有序的tmpp.rvar I,j,t:integer;tmp:listtype;begint:=p;i:=p;j:=q+1;t为tmp指针,I,j分别为左右子序列的指针while (t=r) do beginif (ir) or (ai=aj) 满足取左边序列当前元素的要求then begintmpt:=ai; inc(i);endelse begintmpt:=aj;inc(j);end;inc(t);end;for i:=p to r do ai:=tmpi;end;mergeprocedure merge_sort(var a:listtype; p,r: integer); 合并排序ap.rvar q:integer;beginif pr then beginq:=(p+r-1) div 2;merge_sort (a,p,q);merge_sort (a,q+1,r);merge (a,p,q,r);end;end;mainbeginmerge_sort(a,1,n);end.