ch13 排序

1. 快速排序

快速排序就是将所有元素逐个转换为轴点的过程。轴点必定已然就位，一个序列有序，当且仅当所有元素皆为轴点。

常用的轴点选取策略有随机选取、三者取中。

2. 希尔排序

将整个序列视作一个矩阵，逐列各自排序。

【递减增量】

• 由粗到细：重排矩阵，使其更窄，再次逐列排序
• 逐步求精：如此往复，直至矩阵变成一列，最后一次迭代，等同于全排序

【步长序列】由各矩阵宽度逆向排列而成的序列。

C++

template <typename T> 
void Vector<T>::shellSort(Rank lo, Rank hi) {
    for (Rank d = 0x7FFFFFFF; 0 < d; d >>= 1) //PS Sequence: 1, 3, 7, 15, 31, ...
        for (Rank j = lo + d; j < hi; j++) { //for each j in [lo+d, hi)
            T x = _elem[j]; Rank i = j;//within the prefix of the subsequence of [j]
            while ((lo + d <= i) && (x < _elem[i-d])) //find the appropriate
                _elem[i] = _elem[i-d], i-= d; //predecessor [i]
            _elem[i] = x; //where to insert [j]
        }
}