算法原理：
轴点的概念:任意序列S[lo,hi],对应的有序向量为[lo,hi]。若把S分为前后两个子序列，S[lo,mid)/S[mid,hi)。如果mid为轴点，那么则满足：
- S[mid]=
[mid]
- 前后子序列的成员完全相同
例如：[1,2,4,5,77,88,99]和[4,2,1,5,88,99,77]，那么5就是序列的轴点。
前后序列完成排序后，整体即可排序。采用分治策略，递归完成整个序列排序
不变性：
适应范围：
实际应用：
算法实现：
第一步
template <typename T>//[lo,hi)
void vector<T>::quickSort ( Rank lo, Rank hi )
{
if (hi - lo < 2) return; //递归基
Rank pivotRank = partition(lo, hi - 1);//[lo, hi - 1]
quickSort(lo, pivotRank);//[lo,pivotRank)
quickSort(pivotRank + 1, hi);//[pivotRank+1,hi)
}
第二步
template <typename T>//通过调整元素位置构造区间[lo, hi]的轴点，并返回其秩
Rank vector<T>::partition ( Rank lo, Rank hi )
{
std::swap(_data[lo],_data[rand() % (hi - lo)]);//设置首元素为随机点
T pivot = _data[lo];//轴点
while (lo < hi)
{
while (lo < hi && pivot <= _data[hi])//轴点判断
{
hi--;//右序列左展
}
_data[lo] = _data[hi];//异于轴点，放入对应序列
while (lo < hi && pivot >= _data[hi])
{
lo++;//左序列右展
}
_data[hi] = _data[lo];
}
_data[lo] = pivot;//轴点数据赋值
return lo;
}
算法分析：
| 算法名称 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡 | O( |
O( |
O( |
0(1) | 不稳定 |
算法时间复杂度：
n + (n-1) + (n-2) + ...+2+1
算法优化：
对于重复元素较多的情况，可以针对重复元素进行处理。