探尋快速排序的局限性及其優化策略
一. 快速排序之局限
快速排序的平均時間復雜度為O(nlogn)。其核心步驟是：先從待排序數組中選定一個元素作為基準（pivot），通過一趟排序將數組分成兩部分，使得左邊部分的元素都小于等于基準元素，右邊部分的元素都大于等于基準元素；接著對劃分后的左右子數組分別遞歸進行上述操作，即再次選擇基準元素劃分子數組，持續此過程，直至子數組長度為或，此時整個數組變為有序狀態。
然而，快速排序的性能與基準元素的選取策略緊密相關。若始終選取第一個或最后一個元素作為基準，當輸入數組恰好有序或逆序時，每次劃分都會得到極不均衡的兩個子數組，其中一個子數組可能為空，另一個子數組則幾乎包含所有剩余元素。這將導致快速排序退化為類似冒泡排序的操作，時間復雜度從平均的惡化為 O(n2)。此時，第三方攻擊者可能進行復雜度攻擊，他們刻意構造有序或逆序的輸入數據，使快速排序算法陷入最壞情況的執行路徑，導致算法效率急劇下降。這在對性能要求極高且涉及安全敏感的場景中，可能引發嚴重問題。
二. 優化策略的多維探索
2.1 基準優化的關鍵舉措
隨機基準：隨機選擇基準元素可以減少最壞情況的發生概率。在快速排序中，基準元素的選擇對算法的性能有很大影響。如果每次都選擇固定位置的元素作為基準，例如數組的第一個元素，在某些特殊情況下可能會導致算法的時間復雜度退化為 。而隨機選擇基準元素可以使算法在不同的輸入情況下更加均衡，減少出現極端情況的可能性。
例如，在某些極端情況下，如果輸入的數組已經是有序的，并且每次都選擇第一個元素作為基準，那么快速排序就會退化為冒泡排序，每次只能確定一個元素的位置，時間復雜度為 O(n2)。而通過隨機選擇基準元素，可以打破這種有序性，使得算法能夠更好地發揮分治的優勢，平均時間復雜度為 O(n log n)。
三數取中：選擇數組的第一個元素、最后一個元素和中間元素中的中位數作為基準。這種方法可以避免選擇到極端值作為基準，從而提高算法的穩定性。具體實現時，可以先比較第一個元素、最后一個元素和中間元素的大小，然后選擇中間值作為基準。
例如，對于數組 [8, 1, 4, 9, 6, 3, 5, 2, 7, 0]，首先確定第一個元素為 8，最后一個元素為 0，中間元素為 6。比較這三個元素的大小，得到 0 < 6 < 8，所以選擇 6 作為基準元素。這樣可以避免選擇到 8 或 0 這樣的極端值，使得劃分更加均衡。
2.2 雙軸快排的優勢剖析
雙軸快速排序（Dual - Pivot Quicksort）是快速排序的一種改進形式。其核心思想仍然是基于分治策略，通過選擇兩個樞軸（pivot）元素將數組劃分為三個部分，使得數組元素的分布更加均勻，從而減少在最壞情況下的時間復雜度退化風險，提高排序效率。
2.2.1 雙軸快排的原理與流程
雙軸快速排序會從數組中選擇兩個樞軸元素。一種常見的選擇方法是選擇數組的第一個元素和最后一個元素作為樞軸。例如，對于數組int[] arr = {3, 7, 1, 9, 5}，可能會選擇3（第一個元素）和5（最后一個元素）作為樞軸。這種選擇方式簡單直觀，但也可以采用更復雜的策略來選擇樞軸，以更好地適應不同的數據分布。
第一次劃分：以兩個樞軸為基準，將數組中的元素劃分為三個部分：小于第一個樞軸的元素集合、介于兩個樞軸之間的元素集合、大于第二個樞軸的元素集合。例如，對于數組{3, 7, 1, 9, 5}，假設選擇3和5作為樞軸。在劃分過程中，通過比較元素與樞軸的大小，可能會得到劃分后的結果為{1} {3, 5} {7, 9}。具體的劃分過程是從數組兩端開始向中間掃描，將小于第一個樞軸的元素移到左邊，大于第二個樞軸的元素移到右邊。
遞歸劃分：對劃分后的三個部分分別進行遞歸排序。由于每個部分的元素數量相對原數組可能更均勻，因此可以有效避免像單軸快速排序那樣在最壞情況下（如數組已經有序）時間復雜度退化為。對于上面劃分后的結果{1} {3, 5} {7, 9}，會分別對{1}、{3, 5}和{7, 9}進行遞歸排序。{1}和{7, 9}因為只有一個或兩個元素，本身已經有序或者很容易排序，而對于{3, 5}可以繼續進行雙軸快速排序或者采用簡單的排序方法（如插入排序）來完成排序。
2.2.2 用 Java 實現一個基礎的雙軸快排
package cn.bigcoder.trpcdemo.provider.domain;
import java.util.Arrays;
public class DualPivotQuickSort {
public static void dualPivotQuickSort(int[] arr, int left, int right) {
if (left < right) {
// 選擇兩個樞軸，并進行劃分操作
int[] pivots = partition(arr, left, right);
int pivot1 = pivots[0];
int pivot2 = pivots[1];
// 對小于第一個樞軸的子數組進行遞歸排序
dualPivotQuickSort(arr, left, pivot1 - 1);
// 對介于兩個樞軸之間的子數組進行遞歸排序
dualPivotQuickSort(arr, pivot1 + 1, pivot2 - 1);
// 對大于第二個樞軸的子數組進行遞歸排序
dualPivotQuickSort(arr, pivot2 + 1, right);
}
}
/**
* 雙軸快速排序的分區函數
* @param arr 待排序的數組
* @param left 左邊界索引
* @param right 右邊界索引
* @return 返回兩個樞軸的最終位置
*/
private static int[] partition(int[] arr, int left, int right) {
// 確保左樞軸小于右樞軸
if (arr[left] > arr[right]) {
swap(arr, left, right);
}
int pivot1 = arr[left]; // 左樞軸
int pivot2 = arr[right]; // 右樞軸
int i = left + 1; // 小于左樞軸的元素的右邊界
int j = right - 1; // 大于右樞軸的元素的左邊界
int k = left + 1; // 當前遍歷的元素索引
// 遍歷數組，將元素分到三個區域
while (k <= j) {
if (arr[k] < pivot1) {
// 當前元素小于左樞軸，移到左側
swap(arr, i, k);
i++;
} else if (arr[k] >= pivot2) {
// 當前元素大于等于右樞軸，移到右側
while (arr[j] > pivot2 && k < j) {
j--;
}
swap(arr, k, j);
j--;
// 交換后的元素可能小于左樞軸，需要再次檢查
if (arr[k] < pivot1) {
swap(arr, i, k);
i++;
}
}
k++;
}
// 將樞軸放置到正確的位置
swap(arr, left, i - 1);
swap(arr, right, j + 1);
// 返回兩個樞軸的最終位置
return new int[]{i - 1, j + 1};
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {5, 3, 8, 4, 2, 7};
dualPivotQuickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
2.2.3 雙軸快排的效能優勢
雖然雙軸快速排序在時間復雜度上未超越經典快速排序，但許多語言庫仍用其取代經典快排，原因如下：
經典快速排序在處理部分有序或存在大量重復元素的序列時，可能導致劃分不均勻。例如，若每次選第一個元素為基準，對于某些序列，每次劃分后一個子序列長度可能只減少 1，使遞歸深度接近序列長度。
雙軸快速排序因同時用兩個基準元素劃分，能更好處理此類序列，將序列劃分得更均勻。而且雙軸快速排序的遞歸樹是三叉樹，相比單軸快速排序的二叉樹，在同等數據量下遞歸深度降低，大大減少了排序過程中棧的使用空間和函數調用開銷。
此外，現代計算機存儲系統分層，包括高速緩存（Cache）。排序時若數據訪問連續或局部性好，能更好利用緩存。雙軸快速排序劃分成三個區間，處理后續區間時，數據在內存中分布更規律，更容易被緩存命中；而普通快速排序劃分方式可能導致數據訪問局部性差，緩存未命中情況多，影響排序效率。
關于雙軸快速排序為什么比經典快速排序快，有一篇論文 Why Is Dual-Pivot Quicksort Fast?，有興趣的可以看一下。
2.3 場景適配的算法抉擇
不同排序算法各有擅長場景，常見編程語言會根據場景靈活運用不同排序算法，這種混合排序使語言內置排序函數在多數場景性能良好。
以 Java 語言為例，在 JDK8 提供的 java.util.Arrays#sort(int[]) 的排序方法中根據不同的數據規模以及數組的有序性分別采用快速排序、插入排序、歸并排序。
一般場景下，快速排序因為不需要額外的空間，并且平均時間復雜度和歸并排序一樣，同樣是 O(nlogn)，所以相對于歸并排序更有優勢。
但是當數組基本有序時，快速排序如果基準元素選擇不當，很容易退化為時間復雜度為 O(n2) 的情況，例如每次劃分可能極不均衡。而歸并排序的時間復雜度始終穩定在，不會因為數組的有序狀態而出現性能惡化。在操作過程中，歸并排序的合并階段可以很好地利用數組的基本有序性，比較和移動元素的操作更加高效有序，能夠順勢借助已有的順序完成排序；而快速排序可能因劃分問題無法有效利用已有順序，還可能破壞順序，導致更多的比較和調整操作，所以在此場景下歸并排序更具優勢。
當數組元素數量較少時，插入排序的優勢便凸顯出來。由于快速排序存在遞歸調用的額外開銷，每次遞歸都需保存函數的狀態、參數等各類信息，對于元素較少的數組，這些額外開銷在整體時間成本中所占比重較大，甚至可能超出排序操作本身的時間耗費。而插入排序采用簡單的迭代方式，不存在遞歸調用帶來的額外負擔，其主要操作：比較和移動元素，在小數組環境下相對簡便直接，實際的時間和空間開銷都相對較小，所以在數組元素較少時，插入排序是更為合適的選擇。
三. 總結
本文深入探討了快速排序的局限及語言層面的排序優化思路。快速排序平均時間復雜度為O(nlogn)，但基準選取不當會退化為O(n2)，存在被復雜度攻擊的風險。優化方面，選擇合適基準元素（如隨機基準、三數取中）和采用雙軸快速排序可改善性能，雖雙軸快排在時間復雜度上無提升，但在處理部分有序或大量重復元素序列時，因其三叉樹結構能降低遞歸深度、減少棧空間和函數調用開銷，且數據訪問更易利用緩存，所以被許多語言庫采用。同時，不同編程語言會依場景選擇合適排序算法，如 Java 在 JDK8 的排序方法中，一般場景用快速排序，數組基本有序用歸并排序，數組元素少用插入排序，通過混合排序策略使內置排序函數在多數場景性能出色。
本文參考至：
浙公網安備 33010602011771號