我在研究三路快速排序時(shí)，想出來了一個(gè)點(diǎn)子，使得非三路快速排序也可以高效排序大量重復(fù)元素的數(shù)據(jù)。

原理是這樣的：

單次排序開始前，先設(shè)定一個(gè)狀態(tài)為真

遇到等于基準(zhǔn)值的值時(shí)，如果狀態(tài)為真則與小于基準(zhǔn)值時(shí)做相同的操作，

且無論狀態(tài)為何值都對其進(jìn)行取反并賦回原值。

這樣可以保證遇到了重復(fù)的數(shù)據(jù)時(shí)，重復(fù)數(shù)據(jù)被均勻的分到了基準(zhǔn)值兩側(cè)，從而避免了大量重復(fù)數(shù)據(jù)帶來的嚴(yán)重劃分不均勻，并提高了速度，減少了遞歸深度。

我將其稱作交替快排。

以下為 交替快排、三路快排、普通快排 的不同數(shù)據(jù)情況的速度對比：

可以看出，三路快排在處理大量重復(fù)數(shù)據(jù)情況之外的速度有所下降，而交替快排則基本與普通快排相同。

交替快排對完全隨機(jī)元素進(jìn)行排序時(shí)雖然比普通快排慢一些但是也比三路快排更快。

以下貼出代碼：

以下是用來生成隨機(jī)數(shù)組的代碼：

所以，似乎交替快排比三路快排更加實(shí)用呢！

如果有人有證據(jù)證明這種優(yōu)化方法已經(jīng)被發(fā)明過并發(fā)表了，請聯(lián)系我。

反正我是沒搜到這種優(yōu)化方法。三數(shù)取中我沒用因?yàn)槊菜莆覝y的更慢。多線程優(yōu)化沒加。

插排閾值我設(shè)置的10。尾遞歸優(yōu)化加了，取l與r中間的數(shù)做基準(zhǔn)值優(yōu)化加了，很好用。

有序檢查優(yōu)化沒加，在我常用的場景不太劃算。

不過在已經(jīng)排好的重復(fù)元素多的數(shù)組中，再進(jìn)行排序。

交替快排應(yīng)該會比三路快排有著更多的交換次數(shù)，這倒是可以用交換前先檢查值是否相等來解決，不過這樣會略慢一些，所以根據(jù)需求看你需要減少交換還是提高其它情況下的速度。雖然除了大量重復(fù)依舊比三路快排快。