如有任何值得改进的地方欢迎指出~
快速排序用到了递归的思想。
基本原理
- 将序列首元素作为key，通过双指针法，将key放到它应在的位置（即key前的元素都不大于它，key后的元素都不小于它）
- 对以上一步得到的key的前后两个子序列递归上一步的操作（子序列不再应包括key了QAQ），直至序列长度小于等于1。
算法分析
时间复杂度
最优：此时每一个Key都应位于序列的中间，T(N) = 2T(N/2) + n = O(NlogN)
最坏：此时每一个Key都应位于序列的边上，T(N) = sum of (n - i) from i = 1 to i = n - 1 = O(n^2)
平均：T(N) = O(NlogN)
空间复杂度
快速排序本身空间复杂度为O(1)，其实际取决于递归调用的次数
最优：S(N) = O(logN)
最坏：S(N) = O(N)
平均：S(N) = O(logN)
代码
#include <iostream>
#include <vector>
using namespace std;
template <class T>
void PrintVec(vector<T> &v) {
for (const auto &i: v)
cout << i << " ";
cout << endl;
}
template <class T>
void Swap(T &a, T &b) {
T tmp = a;
a = b;
b = tmp;
}
template <class T>
void QuickSort(vector<T> &v, typename vector<T>::iterator s, typename vector<T>::iterator e) {
if (e - s <= 1) // 若序列长度小于等于1，则无需排序
return ;
typename vector<T>::iterator i = s, j = e - 1;
while (i != j) {
while (i != j && *j >= *s)
j--;
while (i != j && *i <= *s)
i++;
if (i != j)
Swap(*i, *j);
else if (i != s)
Swap(*i, *s);
}
QuickSort(v, s, i);
QuickSort(v, i + 1, e);
}
int main()
{
vector<int> v{3, 2, 1, 4, 5, 9, 7, 0, 6, 8};
QuickSort(v, v.begin(), v.end());
PrintVec(v); //0 1 2 3 4 5 6 7 8 9
return 0;
}
