前几天根据快速排序 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、存在较多的元素交换(每次需要三步),不及改进快速排序法利用空穴赋值方便