C Academy · 课时

快速排序

Q: 「快速排序」这节课中我会学到什么？

分治法 你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

分治法

快速排序 是 CoddyKit 上的免费 C Academy 课时。这是第 2 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 C Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 C Academy 课程共包含 4 节课。

分治

快速排序是一种分治排序算法。它选择一个基准，对数组进行分区，使较小元素位于左侧、较大元素位于右侧，然后递归地对两侧进行排序。

平均时间复杂度为 O(n log n)。

分区步骤

核心思想是分区：围绕基准重新排列数组，使基准左侧的所有元素都更小，右侧的所有元素都更大。随后，基准就位于最终的有序位置。

Lomuto 分区方案

Lomuto方案使用最后一个元素作为基准。它使用索引 i 表示较小元素的边界，并在扫描过程中进行交换。

#include <stdio.h>

int partition(int a[], int lo, int hi) {
    int pivot = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) {
            i++;
            int t = a[i]; a[i] = a[j]; a[j] = t;
        }
    int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
    return i + 1;
}

int main(void) {
    int a[] = {5, 2, 9, 1, 3};
    int p = partition(a, 0, 4);
    printf("pivot index = %d\n", p);
    for (int i = 0; i < 5; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

递归排序

快速排序调用分区函数，然后递归处理基准两侧的两个子数组。基本情况是子数组的大小为 0 或 1。

#include <stdio.h>

int partition(int a[], int lo, int hi) {
    int pivot = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
    int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
    return i + 1;
}

void quicksort(int a[], int lo, int hi) {
    if (lo < hi) {
        int p = partition(a, lo, hi);
        quicksort(a, lo, p - 1);
        quicksort(a, p + 1, hi);
    }
}

int main(void) {
    int a[] = {9, 3, 7, 1, 8, 2, 5};
    quicksort(a, 0, 6);
    for (int i = 0; i < 7; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

选择合适的基准

较差的基准选择（例如对有序输入始终选择最后一个元素）会导致 O(n²) 的性能。更好的选择可以使各个分区更加均衡。

三数取中
随机基准

三数取中

三数取中会选择第一个、中间和最后一个元素的中位数作为基准，从而避免已排序数据上的最坏情况。

#include <stdio.h>

int median_of_three(int a[], int lo, int hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] < a[lo]) { int t=a[mid];a[mid]=a[lo];a[lo]=t; }
    if (a[hi] < a[lo])  { int t=a[hi];a[hi]=a[lo];a[lo]=t; }
    if (a[hi] < a[mid]) { int t=a[hi];a[hi]=a[mid];a[mid]=t; }
    return mid;
}

int main(void) {
    int a[] = {7, 1, 5, 3, 9};
    int m = median_of_three(a, 0, 4);
    printf("median value = %d\n", a[m]);
    return 0;
}

最坏情况分析

如果每次分区都只分出一个元素，递归深度就会达到 n，成本为 O(n²)。当对有序或逆序输入使用固定基准时，就会出现这种情况。

随机化会使最坏情况变得极不可能发生。

随机基准

在分区之前，将一个随机元素交换到基准位置，可以抵御对抗性输入。

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int a[] = {1, 2, 3, 4, 5};
    int lo = 0, hi = 4;
    srand(42);
    int r = lo + rand() % (hi - lo + 1);
    int t = a[r]; a[r] = a[hi]; a[hi] = t; /* move random to pivot slot */
    printf("chosen pivot = %d\n", a[hi]);
    return 0;
}

原地排序且不稳定

快速排序原地完成排序，平均只使用 O(log n) 的栈空间。不过它不稳定：分区时的交换可能改变相等元素的顺序。

尾调用优化

先递归处理较小的一半，再循环处理较大的一半，可以将栈深度限制在 O(log n)，避免大型数组导致栈溢出。

字符串排序

相同的结构可以对任何可比较类型进行排序。这里的快速排序处理整数数组，但只要替换比较操作，也可以处理其他类型。

#include <stdio.h>

int partition(int a[], int lo, int hi) {
    int pivot = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
    int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t; return i + 1;
}
void quicksort(int a[], int lo, int hi) {
    if (lo < hi) { int p = partition(a, lo, hi); quicksort(a, lo, p-1); quicksort(a, p+1, hi); }
}

int main(void) {
    int a[] = {42, -7, 0, 100, 13, 13};
    quicksort(a, 0, 5);
    for (int i = 0; i < 6; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

快速检查

测试您对快速排序的理解。

回顾

您学会了快速排序。

围绕基准进行分区，然后递归处理两侧
平均复杂度为 O(n log n)，最坏情况为 O(n²)
三数取中或随机基准可以避免最坏情况
原地排序，但不稳定

常见问题解答

「快速排序」课时是免费的吗？

是的 — 「快速排序」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 C Academy 课程的其余内容，请升级到 CoddyKit PRO。 C Academy 课程共包含 4 节课。

「快速排序」这节课中我会学到什么？

分治法你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 C Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 C Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 2 节课，共 4 节。

「快速排序」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 C Academy 课中编写并运行代码吗？

能。每节 C Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 C Academy