【排序】快速排序

〇、思想

分治

一、步骤

在数组中选择一个基准 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！