数据结构：快速排序算法(新)
添加时间: 2007-4-9 0:56:17 作者: 程序员认证参考 阅读次数:63 来源: http://www.d9soft.com
根据快速排序 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]; /*大于区间内最后一个元素的值放置ihigh区间内*/
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、存在较多的元素交换（每次需要三步），不及改进快速排序法利用空穴赋值方便
上下文章:
上一篇文章: 数据结构:打印值为x的结点的所有祖先 下一篇文章: 数据结构:栈和递归求两顶点所有简单路径
相关文章: