快速排序详细分析

《快速排序详细分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法与数据结构——快速排序QuickSort页码，1/8快速排序QuickSort我们已经知道，在决策树计算模型下，任何一个基于比较来确定两个元素相对位置的排序算法需要Ω(nlogn)计算时间。如果我们能设计一个需要O(n1ogn)时间的排序算法，则在渐近的意义上，这个排序算法就是最优的。许多排序算法都是追求这个目标。下面介绍快速排序算法，它在平均情况下需要O(nlogn)时间。这个算法是由C.A.R.Hoare发明的。算法的基本思想快速排序的基本思想是基于分治策略的。对于输入的子序列L[p..r]，如果规模足够小则直接进行排序，否

2、则分三步处理：n分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。n递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。n合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。算

3、法的实现算法Quick_Sort的实现：注意：下面的记号L[p..r]代表线性表L从位置p到位置r的元素的集合，但是L并不一定要用数组来实现，可以是用任何一种实现方法（比如说链表），这里L[p..r]只是一种记号。procedureQuick_Sort(p,r:position;varL:List);conste=12;varq:position;begin1ifr-p<=ethenInsertion_Sort(L,p,r)//若L[p..r]足够小则直接对L[p..r]进行插入排序elsebegin2q:=partition(p,

4、r,L);//将L[p..r]分解为L[p..q]和L[q+1..r]两部分3Quick_Sort(p,q,L);//递归排序L[p..q]4Quick_Sort(q+1,r,L);//递归排序L[q+1..r]end;end;对线性表L[1..n]进行排序，只要调用Quick_Sort(1,n,L)就可以了。算法首先判断L[p..r]是否足够小，若足够小则直接对L[p..r]进行排序，Sort可以是任何一种简单的排序法，一般用插入排序。这是因为，对于较小的表，快速排序中划分和递归的开销使得该算法的效率还不如其它的直接排序法好。至于

5、规模多小才算足够小，并没有一定的标准，因为这跟生成的代码和执行代码的计算机有关，可以采取试验的方法确定这个规模阈值。经验表明，在大多数计算机上，取这个阈值为12较好，也就是说，当r-p<=e=12即L[p..r]的规模不大于12时，直接采用插入排序法对L[p..r]进行排序(参见SortingandSearchingAlgorithms:ACookbook)。当然，比较方便的方法是取该阈值为1，当待排序的表只有一个元素时，根本不用排序(其实还剩两个元素时就已经在Partition函数中排好序了)，只要把第1行的if语句该为ifp=r

6、thenexitelse...。这就是通常教科书上看到的快速排序的形式。注意：算法Quick_Sort中变量q的值一定不能等于r，否则该过程会无限递归下去，永远不能结束。因此下文中在partition函数里加了限制条件，避免q=r情况的出现。算法Quick_Sort中调用了一个函数partition，该函数主要实现以下两个功能：1.在L[p..r]中选择一个支点元素pivot;2.对L[p..r]中的元素进行整理，使得L[p..q]分为两部分L[p..q]和L[q+1..r]，并且L[p..q]中的每一个元素的值不大于pivot，L

7、[q+1..r]中的每一个元素的值不小于pivot，但是L[p..q]和Lfile://F:Algorithm=========htm==========算法与数据结构——快速排序Qui...2007-7-5算法与数据结构——快速排序QuickSort页码，2/8[q+1..r]中的元素并不要求排好序。快速排序法改进性能的关键就在于上述的第二个功能，因为该功能并不要求L[p..q]和L[q+1..r]中的元素排好序。函数partition可以实现如下。以下的实现方法是原地置换的，当然也有不是原地置换的方法，实现起来较为简单，这

8、里就不介绍了。functionpartition(p,r:position;varL:List):position;varpivot:ElementType;i,j:position;begin1pivot:=Select_Pivot