快速排序

   快速排序（Quick Sort）是对起跑排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

 

 

初始关键字            49    38    65    97    76    13    27      49

  

                   pivotkey                                               pivotkey

                      ||

进行1次交换状态       49    38    65    97    76    13    27      49         49

                     ↑↑                                           ↓↑←--- ↑

                     i                                     j       j

 

进行1次交换之后       27    38    65    97    76    13            49         49  

                      ↑--------→↑↑                            ↓↑

                      i            i                        j

 

进行2次交换之后       27    38          97    76    13     65     49         49  

                                  ↑↑                 ↓↑←--↑

                                   i                 j     j

 

 

进行3次交换之后       27    38    13    97    76           65     49         49  

                                  ↑-→↑↑             ↓↑

                                  i      i           j

 

进行4次交换之后       27    38    13          76    97     65     49         49  

                                       ↑↑←-------↑

                                        ij          j

完成一趟排序          27    38    13    49    76    97     65     49         49

                                   (a)一趟快排过程

初始状态              {49    38    65    97    76    13     27     49}

一次划分之后          {27    38    13}   49   {76    97    65     49}

分别进行快排          {13}   27   {38}  

                      结束         结束        {49    65}   76    {97}

                                                49   {65}          结束

                                                     结束

有序序列              13    27    38    49    49    65     76     97

 

源代码：


void QSort (SqList &L, int low, int hight){

   //对顺序表L中的子序列L.r[lox...high]作快速排序


   if( low < high ){ //长度大于1


      pivotloc = Partition( L, low, high ); //将L.r[low...high]一分为二


      QSort( L, low, pivotloc - 1 ); //对低子表递归排序，pivotloc是趋轴位置


      QSort( L, pivotloc + 1, high ); //对高子表递归排序


  }

}



int Partition( SqList &L, int low, int high ){

    //交换排序表L中子表r[low...high]的记录，柜轴记录到位，并返回其所在位置，此时在它之前（后）的记录均不大（小）于它


    L.r[0] = L.r[low]; //用子表的第一个记录作柜轴记录


    pivotkey = L.r[low].key; //柜轴记录关键字


    while( low < high ){ //从表的两端交替地向中间扫描


       while( low < high && L.r[high].key >= pivotkey ) --high;

       L.r[low] = L.r[high]; //将比柜轴记录小的移到低端


       while( low < high && L.r[high].key <= pivotkey ) ++low;

       L.r[high] = L.r[low]; //将比柜轴记录大的移到高端


   }

   L.r[low] = L.r[0]; //柜轴记录到位


   return low;

}



void QuickSort( SqList &L ){

  //对顺序表L作快速排序


  QSort( L, 1, L.length );

}