這一章主要講了quick-sort和其改進(jìn)的過程欣喧。下面主要總結(jié)一下改進(jìn)的動機(jī)。
動機(jī)1:
原始的快速排序算法適合于數(shù)字大小隨機(jī)分布的情況。若是一個相同的序列绿聘，那么每次劃分的點都是未劃分點中位置最靠前的點室埋，導(dǎo)致劃分不均勻办绝，時間復(fù)雜度退化到o(n^2)。解決方案：
用兩個指針分別向中間靠攏姚淆，基準(zhǔn)點依然選擇序列中最左側(cè)的點孕蝉，左指針當(dāng)遇到比基準(zhǔn)點大或等于的點就stop，同理右指針遇到比基準(zhǔn)點小或等于的點就stop腌逢，這樣導(dǎo)致劃分點靠近數(shù)字的中間降淮，使得時間復(fù)雜度接近于歸并排序的時間復(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);
}
動機(jī)2:
選取基準(zhǔn)點可以隨機(jī)化動機(jī)3:
對小規(guī)模序列快排效果不如插入排序。所以在動機(jī)1代碼中添加了
if(u - l < threshold)
return;
提前終止排序搏讶，最后再使用插入排序的算法對整體排序佳鳖。
