Algorithm 版 (精华区)

发信人: Lerry (Lerry), 信区: Algorithm
标  题: 快速排序算法（新） 
发信站: 哈工大紫丁香 (2002年03月12日10:52:03 星期二), 站内信件

快速排序算法（新）
前几天根据快速排序 Quick Sort算法的基本思想，编写了如下分治策略的算法，供大家
讨论：
思路：
设输入的序列L[p..r]，确定支点元素l[p]和l[r],并使l[p].key<=l[r].key
分解(Divide)：将序列L[p..r]划分成三个子序列L[p..k-1]、L[k+1..m-1]和L[m+1..r]
，使L[p..q]中关系为L[p..k-1]、l[k]、L[k+1..m-1]、l[m]、L[m+1..r]任一区间元素
的值不大于其后区间元素的值。
递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..k-1]、L[k+1..m-1]和L[m
+1..r]进行排序。
算法的实现（用C语言实现）
QSort(Sqlist &L,int low,int high){
c=high-low;        /*循环次数*/
if(c<10)直接调用插入排序法;    /*小数时直接调用插入排序法*/
if(L.r[low].key>L.r[high].key)L.r[low]<->L.r[high];    /*确保区间内第一个元素
的值不大于区间内最后一个元素的值*/
ilow=low;                /*小于区间内第一个元素的值数组边界下标*/
ihigh=high;            /*大于区间内最后一个元素的值数组边界下标*/
for(i=low+1;i<c;i++){
    if(L.r[i].key<L.r[low].key)L.r[i]<->L.r[++ilow];    /*小于区间内第一个元
素的值放置ilow区间内*/
    else
        if(L.r[i].key>L.r[high].key){
        L.r[i]<->L.r[--ihigh];            /*大于区间内最后一个元素的值放置ih
igh区间内*/
        i--;                            /*下一个比较位置不变*/
        c--;                            /*循环次数减一*/
        }
    }
L.r[ilow]<->L.r[low];            /*将小于区间内第一个元素的边界下标元素与第一
个元素互换*/
L.r[ihigh]<->L.r[high];        /*将大于区间内最后一个元素的边界下标元素与最后
一个元素互换*/
QSort(L,low,ilow-1);
QSort(L,ilow+1,ihigh-1);
QSort(L,ihigh+1,high);
}
void QuickSort(Sqlist &L)
{
QSort(L,1,L.length);
}
优点：
1、每次快速排序将确定二个元素位置
2、每次快速排序将划分三个区间，优化后续平均时间和空间复杂度
缺点：
1、存在较多的元素交换（每次需要三步），不及改进快速排序法利用空穴赋值方便
编制人：陈黎
　

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]