quickqueue.pas

一个快速排序算法的实现例子

{
Quickqueue
Written by Geng Guanhui
}

PROGRAM quickqueue(input,output);
TYPE
  dpointer=^dnodetype;
  dnodetype=RECORD
              data:integer;
              pri,next:dpointer;
              pos:integer;
            END;
VAR
  head,tail,d,i,j,s:dpointer;
  k,n,da:integer;

PROCEDURE queue(i,j,head,tail:dpointer);
  var
    temp:integer;
    he,ta,pos:dpointer;
  begin
    temp:=i^.data;
      while (i^.pos<j^.pos) do
        begin
          while (i^.pos<j^.pos) and (j^.data >= temp) do j:=j^.pri;
          i^.data:=j^.data;
          while (i^.pos<j^.pos) and (i^.data <= temp) do i:=i^.next;
          j^.data:=i^.data;
        end;
    i^.data:=temp;
    pos:=i;
    if i^.pri<>nil then
      begin
        ta:=i^.pri;
        j:=i^.pri;
        j^.next:=nil;
        i^.pri:=nil;
        i:=head;
        if i^.pos=j^.pos then write (i^.data:5)
           else queue(i,j,head,ta);
      end;
    write(temp:5);
    if pos^.next<>nil then
    begin
       i:=pos^.next;
       he:=pos^.next;
       pos^.next:=nil;
       i^.pri:=nil;
       j:=tail;
       if i^.pos=j^.pos then write (i^.data:5)
         else queue(i,j,he,tail);
    end;
  end;


BEGIN
  writeln('Please input the sum of the data');
  readln(n);
  writeln('Please input the data (Integer Only)');
  new(d);
  d^.pri:=nil; d^.next:=nil;
  new(head);
  head^.next:=d; head^.data:=0; head^.pos:=0;
  for k:=1 to n do
    begin
      read(da);
      new(s);
      s^.pri:=nil; s^.next:=nil;
      d^.pos:=k; d^.data:=da; d^.next:=s;
      s^.pri:=d;
      d:=d^.next;
    end;
  head:=head^.next;
  i:=head; j:=d^.pri;
  tail:=d^.pri;
  d^.pri^.next:=nil;
  queue(i,j,head,tail);
  writeln;
  writeln
END.