在數據結構和算法的世界里，排序算法是基石一般的存在。快速排序作為一種高效的排序算法，以其平均情況下的優秀時間復雜度而被廣泛應用。今天，讓我們深入探討快速排序的一種變體——三路劃分的快速排序，看看它是如何在C語言中施展魔法的。
?
快速排序基礎回顧
?
在介紹三路劃分快速排序之前，先來簡單回顧下傳統快速排序。傳統快速排序的核心思想是分治法，選擇一個基準元素，通過一趟排序將待排序列分割成兩部分，其中一部分的元素都比基準元素小，另一部分的元素都比基準元素大，然后分別對這兩部分遞歸地進行排序。
?
傳統快速排序代碼示例
?
c#include <stdio.h>// 交換兩個整數
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 劃分函數
int partition(int arr[], int low, int high) {int pivot = arr[high];int i = (low - 1);for (int j = low; j <= high - 1; j++) {if (arr[j] < pivot) {i++;swap(&arr[i], &arr[j]);}}swap(&arr[i + 1], &arr[high]);return (i + 1);
}// 快速排序函數
void quickSort(int arr[], int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}// 打印數組
void printArray(int arr[], int size) {for (int i = 0; i < size; i++)printf("%d ", arr[i]);printf("\n");
}
?
?
可以使用以下方式調用這個函數：
?
cint main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);printf("初始數組: ");printArray(arr, n);quickSort(arr, 0, n - 1);printf("排序后的數組: ");printArray(arr, n);return 0;
}
?
?
在傳統快速排序中，每次劃分只能確定一個基準元素的最終位置，當數組中存在大量重復元素時，這種方式的效率會受到影響。而三路劃分快速排序就是為了解決這個問題而誕生的。
?
三路劃分快速排序原理
?
三路劃分快速排序，也稱為荷蘭國旗問題的解法（因為它和將紅、白、藍三種顏色的球按順序排列的問題類似）。在三路劃分中，數組被分成三個部分：小于基準元素的部分、等于基準元素的部分和大于基準元素的部分。
?
具體步驟
?
1.?初始化指針：設置三個指針，?lt?（less than）初始指向數組起始位置，?gt?（greater than）初始指向數組末尾位置，?i??初始也指向數組起始位置。
?
2.?遍歷數組：通過 ?i??指針遍歷數組：
?
- 如果 ?arr[i]??小于基準元素，交換 ?arr[i]??和 ?arr[lt]?，然后 ?i??和 ?lt??都向右移動一位。
?
- 如果 ?arr[i]??等于基準元素，?i??直接向右移動一位。
?
- 如果 ?arr[i]??大于基準元素，交換 ?arr[i]??和 ?arr[gt]?，然后 ?gt??向左移動一位，但 ?i??不移動，因為交換過來的 ?arr[gt]??還未比較。
?
3.?遞歸排序：遞歸地對小于基準和大于基準的兩部分進行排序。
?
三路劃分快速排序代碼實現
?
c#include <stdio.h>// 交換兩個整數
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 三路劃分函數
void partition(int arr[], int low, int high, int *lt, int *gt) {int pivot = arr[low];*lt = low;*gt = high;int i = low;while (i <= *gt) {if (arr[i] < pivot) {swap(&arr[*lt], &arr[i]);(*lt)++;i++;} else if (arr[i] > pivot) {swap(&arr[i], &arr[*gt]);(*gt)--;} else {i++;}}
}// 三路劃分快速排序函數
void quickSort3Way(int arr[], int low, int high) {if (low < high) {int lt, gt;partition(arr, low, high, <, >);quickSort3Way(arr, low, lt - 1);quickSort3Way(arr, gt + 1, high);}
}// 打印數組
void printArray(int arr[], int size) {for (int i = 0; i < size; i++)printf("%d ", arr[i]);printf("\n");
}
?
可以使用以下方式調用這個函數：
?
cint main() {int arr[] = {10, 7, 8, 9, 1, 5, 5, 5};int n = sizeof(arr) / sizeof(arr[0]);printf("初始數組: ");printArray(arr, n);quickSort3Way(arr, 0, n - 1);printf("排序后的數組: ");printArray(arr, n);return 0;
}
注意點和要點
?
1.?基準元素的選擇：在上述代碼中，我們選擇數組的第一個元素作為基準元素。在實際應用中，也可以隨機選擇基準元素，以避免最壞情況的發生。
?
2.?邊界條件：在劃分過程中，要注意指針的移動和邊界條件的判斷，確保不會越界。
?
3.?遞歸終止條件：遞歸調用時，要確保遞歸有終止條件，即 ?low < high?，否則會導致棧溢出。
?
4.?性能優勢：三路劃分快速排序在處理包含大量重復元素的數組時，性能明顯優于傳統快速排序，因為它避免了對重復元素的重復排序。
?
總結
?
三路劃分快速排序是一種在特定情況下表現出色的排序算法，通過巧妙的指針操作和劃分策略，它有效地提高了對包含重復元素數組的排序效率。希望通過這篇博客，你對三路劃分快速排序有了更深入的理解，并且能夠在實際應用中靈活運用。在算法的世界里，每一次的探索都像是一場奇妙的冒險，愿你在這個充滿挑戰和驚喜的領域中不斷前行。
)
