快速排序算法详解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//快速排序算法
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;
}