这一章主要讲了quick-sort和其改进的过程。下面主要总结一下改进的动机。
动机1:
原始的快速排序算法适合于数字大小随机分布的情况。若是一个相同的序列，那么每次划分的点都是未划分点中位置最靠前的点，导致划分不均匀，时间复杂度退化到o(n^2)。解决方案：
用两个指针分别向中间靠拢，基准点依然选择序列中最左侧的点，左指针当遇到比基准点大或等于的点就stop，同理右指针遇到比基准点小或等于的点就stop，这样导致划分点靠近数字的中间，使得时间复杂度接近于归并排序的时间复杂度nlog(n)
void qsort(vector<int>& v, int l, int u) {
if (l >= u) return;
int t = v[l]; int i = l; int j = u+1;
while(true) {
do {
i++;
}while(i <= u && v[i] < t);
do {
j--;
}while(v[j] > t);
if (i > j) {
break;
}
swap(v[i], v[j]);
}
swap(v[j], v[l]);
qsort(v, l, i - 1);
qsort(v, i + 1, u);
}
动机2:
选取基准点可以随机化动机3:
对小规模序列快排效果不如插入排序。所以在动机1代码中添加了
if(u - l < threshold)
return;
提前终止排序，最后再使用插入排序的算法对整体排序。
