〇、思想#
- 分治
一、步骤#
- 在数组中选择一個基準 base，將原始數組分為【小於 base】- base -【大於 base】
- 對【小於 base】、【大於 base】兩個數組分別重複步驟 1、2，直到排序完成
二、實現#
void my_qsort(short *arr, int start, int end)
{
if (start >= end) {
return;
}
int i = start;
int j = end;
int base = arr[start];
while (i < j) {
while (arr[j] >= base && i < j) {
j--;
}
while (arr[i] <= base && i < j) {
i++;
}
if (i < j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
arr[start] = arr[i];
arr[i] = base;
my_qsort(arr, start, i - 1);
my_qsort(arr, j + 1, end);
}
三、性能分析#
最壞情況#
如果每次選擇的元素 base 都是要排序元素的最大 / 最小元素，則數組每次排序後確定一個元素的位置，耗時：$\theta (n)$，然後遞歸對一個 n-1 個元素和一個 0 個元素的數組進行快排。運行時間為：$T (n) = T (n-1)+T (0)+\theta (n)$
得時間複雜度為：$O (n^2)$
最好情況#
每次選擇的元素都是數組中間的元素，則數組每次排序後確定一個元素的位置，耗時：$\theta (n)$，然後遞歸對兩個 n/2 的元素進行快排。運行時間為 $T (n) = 2T (n/2)+\theta (n)$
得時間複雜度為：$O (nlogn)$
平均情況#
快排的平均運行時間接近於最好的情況，也就是 $O (nlogn)$
四、優化#
- 快排中基準 base 的選擇會直接影響性能。為此，可以加一個隨機化選取來優化快排
- 對於小數組排序，可以使用其他方法排序
- 使用迭代而非遞歸
Done！
此文由 Mix Space 同步更新至 xLog
原始鏈接為 https://www.vikifish.com/posts/algo/qsort