打ACM的时候自从学会了使用sort()之后，就没有再深究排序了，以至于数据结构考试的时候关于快速排序，希尔排序，堆排序之类的一点不会。
总结（copy）一下算法导论上的知识点。
快速排序的原理
先想一个简单的问题，如何找到数组中的第(k)小
假设我们现在不会排序，会用什么方法呢？
我们可以采用分治的方法，找一个数key，将比key大的放到右边，比key小的放到左边，这样key所处的位置就是key的排名，如果大了说明答案在左边，如果小了说明答案在右边。
现在要求更严格一点，不开辟新的数组怎么做？
/*数组范围是[l,r]*/
key = a[r]
i = l-1;
for(j = l;j < r;++j){
if(a[j] <= key){
++i;
swap(a[j],a[i]);
}
}
swap(a[i+1],a[j])
return i+1;
感性证明一下：
如果a[j]<=key，那么(i)要加一，把这个比key小的(a[j])与(a[i+1])交换；否则j++
可以说在这个过程中保证，i的左边一定是比key小的。
循环结束之后，再把key插入(i+1)的位置，到结束时也保证i的左边一定是比key小的，右边一定是比key大的。（通过循环不变式证明）
学会了上面的方法，现在来看看快速排序
设上面的函数是Partition(l,r)
如果采用下面的方法，我们就可以实现一个快速排序
quickSort(l,r)
if (l >= r) return;
q = Partition(l,r);
quickSort(l,q-1);
quickSort(q+1,r);
快速排序的时间复杂度
- 最坏情况分析
这个算法最坏的情况，就是在已经排好序或者接近排好序的时候。
这时Partition算法划分的某个区间很小，或者没有
导致复杂度很高：
这是一个调和级数，最后的复杂度是(O(n^2))
- 最好情况分析
如果是平均划分，那复杂度非常好。
(T(n) = T(n/2)+T(n/2)+O(n))
这个复杂度是(O(n lgn))
可并不是所有都是最好的情况，如果说最好的情况与最坏的情况交替出现：
复杂度也是(O(n lgn)) 的（略）
有些复杂度的证明挺有意思的，但是太数学了，在这里不打算深究
快速排序的优化
-
随机化
1：随机排列序列中的元素；
2：随机地选择基准元素；
这便是随机化快速排序的思想，这种快排的好处是：其运行时间不依赖于输入序列的顺序 -
三数取中
基于随机化，随机地取三个数，选中位数作为主元
-
栈优化
对于递归很多层的情况，可以进行栈优化
quickSort(l,r)
if (l >= r) return;
while(l<r){
q = Partition(l,r);
quickSort(l,q-1);
l = q+1;
}
-
插入排序优化
当输入数组已经几乎有序的时候，采用插入排序是很快的，如果划分出一个小于k的数组，那么可以直接返回，最后再执行一次插入排序即可。
-
一个短模板
void quick_sort(int l, int r) {
if (l >=r ) return ;
int i = l - 1, j = r + 1, x = a[(l + r) >> 1];
while (i < j) {
do j--; while (a[j] > x);
do i++; while (a[i] < x);
if (i < j) std::swap(a[i], a[j]);
else quick_sort(l, j), quick_sort(j + 1, r);
}
}
STL中的sort()是快排吗
不完全是
感觉是一种取各家之长的排序
他尽量采用了上面所说的优化
- 在数据量很大时采用正常的快速排序，此时效率为O(logN)。
- 一旦分段后的数据量小于某个阈值，就改用插入排序，因为此时这个分段是基本有序的，这时效率可达O(N)。
- 在递归过程中，如果递归层次过深，分割行为有恶化倾向时，它能够自动侦测出来，使用堆排序来处理，在此情况下，使其效率维持在堆排序的O(N logN)，但这又比一开始使用堆排序好。
具体可以看看这篇博客：https://blog.csdn.net/qq_40482358/article/details/80210819