编程珠玑 第十一章总结

这一章主要讲了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;

提前终止排序，最后再使用插入排序的算法对整体排序。