C语言排序——快速排序

原理

是一种基于分治策略的排序算法，运行高效，应用广泛。

快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。

哨兵划分步骤：

选取数组最左端元素作为基准数，初始化两个指针 i 和 j 分别指向数组的两端。
设置一个循环，在每轮中使用 i（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素。
循环执行步骤 2. ，直到 i 和 j 相遇时停止，最后将基准数交换至两个子数组的分界线。

哨兵划分完成后，原数组被划分成三部分：左子数组、基准数、右子数组，且满足“左子数组任意元素 ≤ 基准数 ≤ 右子数组任意元素”。因此，我们接下来只需对这两个子数组进行排序。（哨兵划分的实质是将一个较长数组的排序问题简化为两个较短数组的排序问题。）

快排步骤：

首先，对原数组执行一次“哨兵划分”，得到未排序的左子数组和右子数组。
然后，对左子数组和右子数组分别递归执行“哨兵划分”。
持续递归，直至子数组长度为 1 时终止，从而完成整个数组的排序。

示例

“2 4 1 0 3 5”

代码（C）

// 快速排序类-哨兵划分
int partition(int nums[], int left, int right) {
    // 以 nums[left] 作为基准数
    int i = left, j = right;
    // i 从左向右移动，j 从右向左移动

    while (i < j) {
        while (i < j && nums[j] >= nums[left]) {
            // 从右向左找首个小于基准数的元素
            j--;
        }
        while (i < j && nums[i] <= nums[left]) {
            // 从左向右找首个大于基准数的元素
            i++;
        }
        // 交换这两个元素
        swap(nums, i, j);
        // 继续寻找满足条件的元素进行交换
    }

    // 将基准数交换至两子数组的分界线
    swap(nums, i, left);
    // 返回基准数的索引
    return i;
}

// 快速排序类-快速排序
void quickSort(int nums[], int left, int right) {
    // 子数组长度为 1 时终止递归
    if (left >= right) {
        return;
    }
    // 哨兵划分
    int pivot = partition(nums, left, right);
    // 递归左子数组、右子数组
    quickSort(nums, left, pivot - 1);
    quickSort(nums, pivot + 1, right);
}

复杂度

时间复杂度：最差情况为 $O(n logn)$

空间复杂度：为 $O(n)$

优化哨兵划分中的基准数的选取策略

若输入数组是完全倒序的，由于我们选择最左端元素作为基准数，那么在哨兵划分完成后，基准数被交换至数组最右端，导致左子数组长度为 𝑛 - 1、右子数组长度为 0 。如此递归下去，每轮哨兵划分后的右子数组长度都为 0 ，分治策略失效，快速排序退化为“冒泡排序”。

于是可以优化哨兵划分中的基准数的选取策略，可以在数组中选取三个候选元素（通常为数组的首、尾、中点元素），并将这三个候选元素的中位数作为基准数。

尾递归优化

防止栈帧空间的累积，我们可以在每轮哨兵排序完成后，比较两个子数组的长度，仅对较短的子数组进行递归。

void quickSortTailCall(int nums[], int left, int right) {
    // 子数组长度为 1 时终止
    while (left < right) { 
        // 哨兵划分操作
        int pivot = partition(nums, left, right);
        // 确定左右子数组哪个更短
        if (pivot - left < right - pivot) {
            // 如果左子数组更短，递归排序左子数组
            quickSortTailCall(nums, left, pivot - 1); 
            // 然后将左指针移动到右子数组的起始位置，继续处理右子数组
            left = pivot + 1; 
        } else {
            // 如果右子数组更短，递归排序右子数组
            quickSortTailCall(nums, pivot + 1, right); 
            // 将右指针移动到左子数组的结束位置，继续处理左子数组
            right = pivot - 1; 
        }
    }
}