PASCAL语言多种排序算法源程序

6种排序算法的源程序

PASCAL语言多种排序算法源程序

1.快速排序：

procedure qsort(l,r:integer);

var i,j,mid:integer;

begin

i:=l;j:=r; mid:=a[(l+r) div 2]; {将当前序列在中间位置的数定义为中间数} repeat

while a[i]<mid do inc(i); {在左半部分寻找比中间数大的数} while a[j]>mid do dec(j);{在右半部分寻找比中间数小的数}

if i<=j then begin {若找到一组与排序目标不一致的数对则交换它们} swap(a[i],a[j]);

inc(i);dec(j); {继续找}

end;

until i>j;

if l<j then qsort(l,j); {若未到两个数的边界，则递归搜索左右区间} if i<r then qsort(i,r);

end;{sort}

2.插入排序：

思路：当前a[1]..a[i-1]已排好序了，现要插入a[i]使a[1]..a[i]有序。 procedure insert_sort;

var i,j:integer;

begin

for i:=2 to n do begin

a[0]:=a[i];

j:=i-1;

while a[0]<a[j] do begin

a[j+1]:=a[j];

j:=j-1;

end;

a[j+1]:=a[0];

end;

end;{inset_sort}

3.选择排序：

procedure sort;

var i,j,k:integer;

begin

for i:=1 to n-1 do

for j:=i+1 to n do

if a[i]>a[j] then swap(a[i],a[j]);

6种排序算法的源程序

end;

4. 冒泡排序

procedure bubble_sort;

var i,j,k:integer;

begin

for i:=1 to n-1 do

for j:=n downto i+1 do

if a[j]<a[j-1] then swap( a[j],a[j-1]); {每次比较相邻元素的关系} end;

5.堆排序：

procedure sift(i,m:integer);{调整以i为根的子树成为堆,m为结点总数} var k:integer;

begin

a[0]:=a[i]; k:=2*i;{在完全二叉树中结点i的左孩子为2*i,右孩子为2*i+1} while k<=m do begin

if (k<m) and (a[k]<a[k+1]) then inc(k);{找出a[k]与a[k+1]中较大值} if a[0]<a[k] then begin a[i]:=a[k];i:=k;k:=2*i; end

else k:=m+1;

end;

a[i]:=a[0]; {将根放在合适的位置}

end;

procedure heapsort;

var

j:integer;

begin

for j:=n div 2 downto 1 do sift(j,n);

for j:=n downto 2 do begin

swap(a[1],a[j]);

sift(1,j-1);

end;

end;

6. 归并排序

{a为序列表，tmp为辅助数组}

procedure merge(var a:listtype; p,q,r:integer);

{将已排序好的子序列a[p..q]与a[q+1..r]合并为有序的tmp[p..r]} var I,j,t:integer;

tmp:listtype;

begin

t:=p;i:=p;j:=q+1;{t为tmp指针，I,j分别为左右子序列的指针} while (t<=r) do begin

if (i<=q){左序列有剩余} and ((j>r) or (a[i]<=a[j])) {满足取左边序列当前元素的要求}

6种排序算法的源程序

then begin

tmp[t]:=a[i]; inc(i);

end

else begin

tmp[t]:=a[j];inc(j);

end;

inc(t);

end;

for i:=p to r do a[i]:=tmp[i];

end;{merge}

procedure merge_sort(var a:listtype; p,r: integer); {合并排序a[p..r]} var q:integer;

begin

if p<>r then begin

q:=(p+r-1) div 2;

merge_sort (a,p,q);

merge_sort (a,q+1,r);

merge (a,p,q,r);

end;

end;

{main}

begin

merge_sort(a,1,n);

end.