〇、思想#
- 分治
一、步骤#
- 在数组中选择一个基准 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