TB椰程 TypeBuddy 打字搭子

快速排序

CSP-J · 编程模板 · 代码 · cpp · 难度 4/5 · 共 615 字

以基准值分左右两段，递归处理

  • 排序
  • 分治

前置内容

正文

// ── 快速排序：分治 ──
// 选基准，小的甩左、大的甩右
// 再递归两侧
void quick_sort(int a[], int l, int r) {
    // 0/1 个元素天然有序
    if (l >= r) return;
    // 取中间元素当基准
    int mid = a[(l + r) / 2];
    int i = l, j = r;
    while (i <= j) {
        // 从左找第一个 >= 基准的
        while (a[i] < mid) i++;
        // 从右找第一个 <= 基准的
        while (a[j] > mid) j--;
        // 一左一右交换，双双推进
        if (i <= j) {
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
            i++;
            j--;
        }
    }
    // 递归左半段
    quick_sort(a, l, j);
    // 递归右半段
    quick_sort(a, i, r);
}
// 平均 O(n log n)
// 每次只切一个元素会退化 O(n^2)

CSP-J · 编程模板的其它内容

打字首页 · 词库画廊 · 编程打字 · 指法入门 · 天梯榜 · 数据分析 · 班级课堂 · 关于我们
椰程 TypeBuddy 打字搭子 —— 键盘指法练习 · 单词记忆 · 班级课堂 · 在线 PK