這一章主要講了quick-sort和其改進(jìn)的過程。下面主要總結(jié)一下改進(jìn)的動(dòng)機(jī)。

• 動(dòng)機(jī)1:
  原始的快速排序算法適合于數(shù)字大小隨機(jī)分布的情況。若是一個(gè)相同的序列，那么每次劃分的點(diǎn)都是未劃分點(diǎn)中位置最靠前的點(diǎn)，導(dǎo)致劃分不均勻，時(shí)間復(fù)雜度退化到o(n^2)。

• 解決方案：
  用兩個(gè)指針分別向中間靠攏，基準(zhǔn)點(diǎn)依然選擇序列中最左側(cè)的點(diǎn)，左指針當(dāng)遇到比基準(zhǔn)點(diǎn)大或等于的點(diǎn)就stop，同理右指針遇到比基準(zhǔn)點(diǎn)小或等于的點(diǎn)就stop，這樣導(dǎo)致劃分點(diǎn)靠近數(shù)字的中間，使得時(shí)間復(fù)雜度接近于歸并排序的時(shí)間復(fù)雜度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);
}

• 動(dòng)機(jī)2:
  選取基準(zhǔn)點(diǎn)可以隨機(jī)化

• 動(dòng)機(jī)3:
  對小規(guī)模序列快排效果不如插入排序。所以在動(dòng)機(jī)1代碼中添加了

if(u - l < threshold)
  return;

提前終止排序，最后再使用插入排序的算法對整體排序。