快速排序算法详解

原理

选择一个元素作为轴点，使用轴点构造算法对原序列进行改造，使得位于轴点前的元素均不大于轴点，位于轴点后的元素均不小于轴点，再以轴点为界，分别递归地对前后子序列进行快速排序。

代码

//快速排序算法
template <class T>
void Vector<T>::quickSort(Rank lo, Rank hi)
{
    if (hi - lo < 2) // 单元素情况，即递归基
        return;
    Rank mi = partition(lo, hi - 1); // 在[lo,hi-1]内构造轴点
    quickSort(lo, mi); // 对前缀递归排序
    quickSort(mi + 1, hi); // 对后缀递归排序
}

//轴点构造算法
template <class T>
Rank Vector<T>::partition(Rank lo, Rank hi)
{
    std::swap(_elem[lo], _elem[lo + rand() % (hi - lo + 1)]); //使得抽取的数是均匀分布的
    T pivot = _elem[lo]; //以首元素为候选轴点
    while (lo < hi)
    {
        while ((lo < hi) && (pivot <= _elem[hi])) // 从后往前移动要比较的元素，如果不是大于轴点就跳出
            hi--;
        _elem[lo] = _elem[hi]; //将不大于轴点的值转到秩为lo的元素
        while ((lo < hi) && (_elem[lo] <= pivot)) //从前往后移动要比较的元素，如果不是小于轴点就跳出
            lo++;
        _elem[hi] = _elem[lo]; //将不小于轴点的值转到之前移动到的秩为hi的元素
    } // lo == hi

    _elem[lo] = pivot; //将中间的最后一个值，赋值为pivot
    return lo;
}

实例

最后

以上就是欢呼信封为你收集整理的快速排序算法详解的全部内容，希望文章能够帮你解决快速排序算法详解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。