设计文档.txt

来自「一个快速排序算法的实现例子」· 文本 代码 · 共 100 行

by 耿关辉

===========================================================================================================================
问题描述： 
    在双向链表上实现快速排序的递归算法。
问题分析： 
   课本中的快速排序算法并不是用链表来实现递归的目的的，所以要解决以上的问题，就要另外定义相关的数据类型的定义，
并依照快速排序算法的思想来进行程序的实现。

===========================================================================================================================

算法设计思想和实现的方法：

依照原先的问题分析：算法的实现分为以下几个步骤：

    （1）相关的数据类型的定义： 
           TYPE
             dpointer=^dnodetype;
             dnodetype=RECORD                //双向链表的数据结构类型的定义
                         data:integer;         //存储结点的数据,即数据域data
                         pos:integer;
                         pri,next:dpointer;        //指向前去结点和后继结点指针pri,next
                       END;
           VAR 
             head,tail,d,i,j,s:dpointer;
             h,n,ta,pos:integer; 

    （2）数据的输入：
           writeln('Please input the number of the  data');   //输入输入的数据的数目n
           readln(n);
           writeln('Please input the data');          //开始输入全部的数据
           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;        //相应的指针随位置向后推移
                 d^.pri:=d;
                 d:=d^.next;
              end;

     (3)快速排序算法的实现以及结果的输出：
          PROCEDURE   quick(i,j,head,tail:dpointer);
            //快速排序的基本思想是：首先通过一趟排序将输入的待排序列分割成为独立的两部分，
            //使得其中的一部分记录的关键字均比另一部分记录的关键字要小，
            //然后运用递归的方法在分别对形成的两个部分进行快速排序，从而达到使整个序列有序。
            //本算法在对输入的数据记录进行递归的快速排序，执行本算法之后，会使得待排的序列分割成为两个部分，
            //由于递归的方法的应用，从而最终达到快速排序的目的。

           temp:=i^.data;
             while (i^.pos<j^.pos) do              //判断条件：当i^.pos<j^.pos时，执行下列程序段
                begin
                  while (i^.pos<j^.pos) and (j^.data>=temp) do   j:=j^.pri;              //j指针向前移动
                  i^.data:=j^.data;
                  while (i^.pos<j^.pos) and (i^.data<=temp) do i:=i^.next;               //i指针向后移动
                  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 quick(i,j,head,ta);                       //递归过程quick(*,*,*,*)的应用
               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 quick(i,j,he,tail);                         //递归过程quick(*,*,*,*)的应用                          
             end;
        ENDP;    {quick}
===========================================================================================================================
结果测试实例： 
   Please input the number of the data:9
   Please input the data:
    12 54 65 12 75 10 32 151 89
结果:
    10 12 12 32 54 65 75 89 151