一 冒泡排序  稳定

[算法描述]
所给的N个数中,先拿第一个数来和第二个比较,然后让较大的一个排在后面(即如果N1>N2,则让N1与N2交换位置),然后又拿第二个数来和第三个数比较,又把较大的一个排在后面,如此往下做下去,直到第N-1个数和第N个数比较完后,最大的那个数就会被升到了最后面来.接下来又照同样的方法来把前N-1个数中最大的数排到第N-1的位置上,做到最后,整一列数都被排好了. 不过下面的代码和上面描述的相反,是从后面开始比较的.

[源程序]
方案一:
for i:=1 to (n-1) do
  for j:=n downto (i+1) do
    if a[j-1]>a[j] then  //降序:a[j-1]     begin
      k:=a[j-1];
      a[j-1]:=a[j];
      a[j]:=k;
    end;
方案二:
for i:=1 to (n-1) do
  for j:=(i+1) to n do
    if a[i]>a[j] then  //降序:a[i]     begin
      k:=a[i];
      a[i]:=a[j];
      a[j]:=k;
    end;

二 选择排序  不稳定

[算法描述]
第一趟扫描所有数据,选择其中最小的一个与第一个数据互换;第二趟从第二个数据开始向后扫描,选择最小的与第二个数据互换;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程.

[源程序]
for i:=1 to (n-1) do
begin
  k:=i;
  for j:=(i+1) to n do
    if a[j]a[k]
  x:=a[i];
  a[i]:=a[k];
  a[k]:=x;
end;

三 插入排序  稳定

思路：当前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+1]:=a[j];
j:=j-1;
      end;
      a[j+1]:=a[0];
    end;
  end;

四 快速排序  不稳定

[算法描述]
设有一无序数组a有n个元素.
1.以数组a的中点元素为参考值;
2.将中点左边大于(或小于)参考值的与中点右边小于(或大于)参考值的元素互换位置;
3.对中点左边的元素执行快排操作;
4.对中点右边的元素执行快排操作.

[源程序]
procedure qsort(var a:arraytype; lx,rx:longint);
var i,j,t,x:longint;
begin
      i:=lx; j:=rx;
      x:=a[random(j-i+1)+i];
      repeat
            while (a[i]x
            while (a[j]>x) do dec(j); //降序:x>a[j]
            if (i<=j) then
            begin
                  t:=a[i]; a[i]:=a[j]; a[j]:=t; //如果是为记录数组排序的话,t必须是记录类型的
                  inc(i);  dec(j);
            end;
      until (i>j);
      if (lx       if (i end;

五 堆排序  不稳定
procedure heap(var r:arrtype;nn,ii:integer);   {该过程为调整为大根堆的过程，大根堆排序后是 min to max }
  var x,i,j:integer;
  begin
    i:=ii;
    x:=r[ii];
    j:=2*ii;
    while j<=nn do
      begin
        if (jr[j+1])}
        if xr[j]}
          else j:=nn+1;
      end;
      r[i]:=x;
     a:=r;
  end;

procedure heapsort(n:integer);   {堆排序}
  for i:=n div 2 downto 1 do     {建立初始堆，且产生最大值a[1]}
    heap(a,n,i);
  for i:=n downto 2 do           {将当前最值交换到最终位置上，再对前i-1个数调整}
    begin
      temp:=a[1]; a[1]:=a[i]; a[i]:=temp;
      heap(a,i-1,1);
    end;                         

六 归并排序  稳定
{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])) {满足取左边序列当前元素的要求}
        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.