Algorithm 版 (精华区)

发信人: zjliu (秋天的萝卜), 信区: Algorithm
标  题: 快速排序
发信站: 哈工大紫丁香 (Wed Aug 13 16:06:05 2003)

快速排序
快速排序是通过比较关键码、交换记录，以某个记录为界(该记录称为支点)，将待排序

列分成两部分。其中，一部分所有记录的关键码大于等于支点记录的关键码，另一部分

所有记录的关键码小于支点记录的关键码。我们将待排序列按关键码以支点记录分成两

部分的过程，称为一次划分。对各部分不断划分，直到整个序列按关键码有序。
一次划分方法：
    设1≤p<q≤n，r[p],r[p+1],...,r[q]为待排序列
   ① low=p；high=q；  //设置两个搜索指针，low是向后搜索指针，high是向前搜索

指针
      r[0]=r[low]；     //取第一个记录为支点记录，low位置暂设为支点空位
   ② 若low=high，支点空位确定，即为low。
      r[low]=r[0]；                //填入支点记录，一次划分结束
      否则，low<high，搜索需要交换的记录，并交换之
   ③ 若low<high且r[high].key≥r[0].key //从high所指位置向前搜索，至多到low+

1位置
       high=high-1；转③                  //寻找r[high].key<r[0].key
       r[low]=r[high]；       //找到r[high].key<r[0].key，设置high为新支点位

置，
                                  //小于支点记录关键码的记录前移。
   ④ 若low<high且r[low].key<r[0].key //从low所指位置向后搜索，至多到high-1位

置
       low=low+1；转④        //寻找r[low].key≥r[0].key
       r[high]=r[low]；       //找到r[low].key≥r[0].key，设置low为新支点位置

，
                                   //大于等于支点记录关键码的记录后移。
       转②             //继续寻找支点空位
【算法10.7】
int Partition(S_TBL *tbl,int low,int high)  /*一趟快排序*/
{   /*交换顺序表tbl中子表tbl->[low…high]的记录，使支点记录到位，并反回其所在

位置*/
     /*此时，在它之前(后)的记录均不大(小)于它*/
 tbl->r[0]=tbl->r[low];   /*以子表的第一个记录作为支点记录*/
 pivotkey=tbl->r[low].key;  /*取支点记录关键码*/
 while(low<higu)    /*从表的两端交替地向中间扫描*/
 { while(low<high&&tbl->r[high].key>=pivotkey)  high--;
  tbl->r[low]=tbl->r[high]; /*将比支点记录小的交换到低端*/
  while(low<high&&tbl-g>r[high].key<=pivotkey)  low++;
  tbl->r[low]=tbl->r[high]; /*将比支点记录大的交换到低端*/
 }
 tbl->r[low]=tbl->r[0];     /*支点记录到位*/
 return low;    /*反回支点记录所在位置*/
}
【例10.5】一趟快排序过程示例
    r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] r[9] r[10]  存储单元
     49   14   38   74   96   65    8   49   55   27    记录中关键码
low=1；high=10； 设置两个搜索指针， r[0]=r[low]；  支点记录送辅助单元，
     □   14   38   74   96   65    8   49   55   27
     ↑                                            ↑
     low                                           high
第一次搜索交换
    从high向前搜索小于r[0].key的记录，得到结果
     27   14   38   74   96   65    8   49   55   □
     ↑                                            ↑
     low                                           high
    从low向后搜索大于r[0].key的记录，得到结果
     27   14   38   □   96   65    8   49   55   74
                    ↑                             ↑
                    low                            high
第二次搜索交换
    从high向前搜索小于r[0].key的记录，得到结果
     27   14   38     8   96   65   □   49   55   74
                     ↑             ↑
                     low            high
    从low向后搜索大于r[0].key的记录，得到结果
     27   14   38     8   □   65   96   49   55   74
                          ↑        ↑
                          low       high
第三次搜索交换
    从high向前搜索小于r[0].key的记录，得到结果
     27   14   38     8   □   65   96   49   55   74
                         ↑↑
                       low  high
    从low向后搜索大于r[0].key的记录，得到结果
     27   14   38     8   □   65   96   49   55   74
                         ↑↑
                       low  high
low=high，划分结束，填入支点记录
     27   14   38     8   49   65   96   49   55   74
【算法10.8】
void  QSort(S_TBL *tbl,int low,int high)  /*递归形式的快排序*/
{ /*对顺序表tbl中的子序列tbl->[low…high]作快排序*/
 if(low<high)
 { pivotloc=partition(tbl,low,high); /*将表一分为二*/
  QSort(tbl,low,pivotloc-1);  /*对低子表递归排序*/
  QSort(tbl,pivotloc+1,high);  /*对高子表递归排序*/
 }
}
【效率分析】
     空间效率：快速排序是递归的，每层递归调用时的指针和参数均要用栈来存放，递

归调用层次数与上述二叉树的深度一致。因而，存储开销在理想情况下为O(log2n)，即

树的高度；在最坏情况下，即二叉树是一个单链，为O(n)。
    时间效率：在n个记录的待排序列中，一次划分需要约n次关键码比较，时效为O(n)

，若设T(n)为对n个记录的待排序列进行快速排序所需时间。
    理想情况下：每次划分，正好将分成两个等长的子序列，则
       T(n)≤cn+2T(n/2)                 c是一个常数
           ≤cn+2(cn/2+2T(n/4))=2cn+4T(n/4)
           ≤2cn+4(cn/4+T(n/8))=3cn+8T(n/8)
          ······
           ≤cnlog2n+nT(1)=O(nlog2n)
    最坏情况下：即每次划分，只得到一个子序列，时效为O(n2)。
快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初

始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以"三

者取中法"来选取支点记录，即将排序区间的两个端点与中点三个记录关键码居中的调整

为支点记录。快速排序是一个不稳定的排序方法。

--
╔═══════════════════╗
║★★★★★友谊第一  比赛第二★★★★★║
╚═══════════════════╝

※ 来源:．哈工大紫丁香 bbs.hit.edu.cn [FROM: 202.118.229.162]