- 分解算法:每趟运算确保比枢轴pivot小的值都在其左边,大的都在右边。
int Partition(SqList &L, int low, int high)
{
L.r[0] = L.r[low];//子表中的第一个记录作为枢轴记录
int pivot = L.r[low].key;//枢轴记录的关键字值
while (low < high)
{
while (low < high && L.r[high].key>pivot)
{
high--;
}
L.r[low].key = L.r[high].key;
while (low < high && L.r[low].key<pivot)
{
low++;
}
L.r[high].key = L.r[low].key;
}
L.r[low] = L.r[0];
return low;
}
- 求解过程:递归调用分解函数的过程。
void QSort(SqList &L,int low,int high)
{ // 对顺序表L中的子序列L.r[low..high]作快速排序。算法10.7
int pivotloc;
if(low<high)
{ // 长度大于1
pivotloc=Partition(L,low,high); // 将L.r[low..high]一分为二
QSort(L,low,pivotloc-1); // 对低子表递归排序,pivotloc是枢轴位置
QSort(L,pivotloc+1,high); // 对高子表递归排序
}
}
评论