快速排序
快速排序是一種基於分而治之演算法的高效排序演算法。快速排序的工作原理是圍繞一個選定的中軸元素將陣列分割成兩個部分。它將較小的元素移到中軸的左側，較大的元素移到右側。之後，左右兩部分遞迴排序，對整個陣列進行排序。之所以稱為快速排序，是因為它比常見的排序演算法快了約 2 或 3 倍。快速排序廣泛應用於資料結構內部的資訊搜尋和數值計算。
快速排序演算法
假設我們有一個無序陣列 A[]，包含 n 個元素。取兩個變數 beg 和 end，然後儲存開始和結束元素的索引。
Partition()
-
選擇最後一個元素(可以是任何元素，取決於實現)作為中軸元素。
-
初始化指標
i的值為beg - 1，這樣我們就可以把小於中軸的元素移到陣列的起始位置。 -
迭代遍歷陣列，並對每個元素做如下操作。
-
如果元素
A[i]<pivot，則遞增i並將A[i]與A[j]交換。 -
將
A[i]與A[end]互換，使中軸元素處於正確的位置。 -
返回中軸元素的索引。
QuickSort()
-
選擇中軸索引
pi。 -
圍繞中軸索引對陣列進行分割槽。
-
在中軸元素的左側
arr[beg,...,pi]遞迴排序元素。 -
在中軸元素的右側
arr[pi+1,...,end]上對元素進行遞迴排序。
快速排序示例
假設我們有一個陣列：(6,5,1,4,2,3)。我們將使用快速排序演算法對其進行排序。
-
首先選擇
3作為中軸元素，將陣列分成兩個子部分(1,2)- 較小的元素，和(6,5,4)- 較大的元素。然後將3放在其排序位置。然後對形成的兩個子陣列進行遞迴排序。 -
對於子陣列
(1,2)，選擇2作為中軸元素並放在正確的位置，然後形成已經排序的子陣列(1)。 -
對於子陣列
(6,5,4)，4被放在排序後的位置，形成子陣列(6,5)，然後遞迴排序。 -
對於子陣列
(6,5)，選擇5作為支點，放到正確的位置，從而得到(6)作為新的子陣列。單元素子陣列(6)已經被排序了。 -
最後，我們得到排序後的陣列為
(1，2，3，4，5，6)。
快速排序演算法實現
#include <bits/stdc++.h>
using namespace std;
int partition(int arr[], int beg, int end) {
// Select the last element as pivot element
int pivot = arr[end];
int i = (beg - 1);
// Move smaller elements to left side and larger on right side
for (int j = beg; j < end; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1],
arr[end]); // Move pivot element to its right position in array
return (i + 1);
}
void quickSort(int arr[], int beg, int end) {
if (beg < end) {
int pi = partition(arr, beg, end);
quickSort(arr, beg,
pi - 1); // Recursive Sort element on left side of partition
quickSort(arr, pi + 1,
end); // Recursive Sort element on right side of partition
}
}
int main() {
int n = 6;
int arr[6] = {5, 3, 4, 2, 1, 6};
cout << "Input array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
quickSort(arr, 0, n - 1); // Sort elements in ascending order
cout << "Output array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
快速排序演算法的複雜度
時間複雜度
- 平均情況
快速排序所需時間由以下遞推關係給出。
T(n) = T(k) + T(n-k-1) + θ(n)
這裡的 k 代表比中軸元素小/大的元素數，這個遞迴關係的結果是 T(n) = nLogn。
這個遞迴關係的結果給出了 T(n)=nLogn.當我們得到隨機的不均衡分割槽時，就會出現平均情況。時間複雜度是 [Big Theta]：O(nLogn)。
- 最壞情況
T(n) = T(n-1) + θ(n)
最壞的情況是，中軸元素總是陣列中最大或最小的元素。在這種情況下，所有元素都落在一個子陣列中，必須進行最大的 n 呼叫。最壞情況下的時間複雜度是[大 O]。O(n2)。
- 最佳情況
T(n) = 2T(n/2) + θ(n)
最好的情況是，當所選的中軸元素總是中間元素，或者當兩個分割槽均勻平衡時，即大小相差 1 或更小。最佳情況下的時間複雜度為 [Big Omega]：O(nLogn)。
空間複雜度
快速排序演算法的平均情況下空間複雜度為 O(Logn)。這是遞迴棧所需要的空間。但在最壞的情況下，當排序一個陣列需要 n 遞迴時，空間複雜度是 O(n)。
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn