🔥Flumina Blog

主题

00:00:00
🔥Flumina2025-11-28 15:27:002026-08-29 15:06:03算法笔记AcWingBase算法笔记C++AlgorithmData Structure
1552
7.1m
0

文章发布较早，内容可能过时，阅读注意甄别。

快速排序三种实现方式对比分析 ​

说明：以下三种方法均基于 C++ 实现，适用于标准快速排序场景。所有代码均可在本地编译运行，并在 Typora 中完美渲染。

来源题目/题单说明
牛客https://www.nowcoder.com/practice/3385982ae71d4a1ca8bf3d03614c0325快速排序
牛客https://www.nowcoder.com/practice/34731183c31e4276b2d081590b2f3a4b排序（快速排序）
洛谷https://www.luogu.com.cn/problem/T588555T588555 快速排序
洛谷https://www.luogu.com.cn/problem/U223702U223702 快速排序
洛谷https://www.luogu.com.cn/problem/T292012T292012 【模板】快速排序
洛谷https://www.luogu.com.cn/problem/T588555T588555 快速排序
洛谷https://www.luogu.com.cn/problem/T318859T318859 Quick Sort快排

一、总体概览 ​

特性quickSort1quickSort2quickSort3
分区方式基于值的单向扫描 + 随机 pivot双向指针（Hoare 分区）三路快排（Dijkstra 三分法）
Pivot 选择随机选取元素值中间位置元素中间位置元素
重复元素优化❌❌✅
平均时间复杂度O(nlog⁡n)O(nlog⁡n)O(nlog⁡n)，大量重复时接近 O(n)
是否推荐⚠️ 谨慎✅ 推荐✅（修正后）

二、方法一：quickSort1 —— 基于值的随机 Partition（Lomuto 变种） ​

✅ 完整可运行代码 ​

cpp
#include <cmath>
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
int nums[N];

// Partition 函数：将 <= x 的元素移到左边，并确保一个 x 落在最终位置
int Partition(int l, int r, int x) {
  int a = l, xi = l;
  for (int i = l; i <= r; i++) {
    if (nums[i] <= x) {
      swap(nums[a], nums[i]);
      if (nums[a] == x) { xi = a; }
      a++;
    }
  }
  swap(nums[xi], nums[a - 1]);  // 将一个 x 放到正确位置
  return a - 1;
}

void quickSort1(int l, int r) {
  if (l >= r) return;
  // 随机选择一个下标，取其值作为 pivot
  int rand_index = l + rand() % (r - l + 1);
  int x = nums[rand_index];
  int p = Partition(l, r, x);
  quickSort1(l, p - 1);
  quickSort1(p + 1, r);
}

int main() {
  srand(time(0));  // 初始化随机种子
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) { scanf("%d", &nums[i]); }
  quickSort1(0, n - 1);
  for (int i = 0; i < n; i++) { printf("%d ", nums[i]); }
  return 0;
}

⚠️ 注意事项 ​

  • 虽然引入了随机化，但对重复元素处理不完善。
  • 在极端重复数据下可能性能退化或行为异常。
  • 不建议用于生产环境。

三、方法二：quickSort2 —— 经典 Hoare 分区（双向指针） ​

✅ 完整可运行代码 ​

cpp
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
int nums[N];

void quickSort2(int l, int r) {
  if (l >= r) return;
  int i = l - 1, j = r + 1;
  // int x = nums[l + ((r - l) >> 1)];  // 取中间元素为 pivot
  int x = nums[l + rand() % (r - l + 1)];  // 随机选择一个下标 为 pivot (推荐)
  while (i < j) {
    do { i++; } while (nums[i] < x);
    do { j--; } while (nums[j] > x);
    if (i < j) { swap(nums[i], nums[j]); }
  }
  // 注意：Hoare 分区返回的是 j，递归 [l, j] 和 [j+1, r]
  quickSort2(l, j);
  quickSort2(j + 1, r);
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) { scanf("%d", &nums[i]); }
  quickSort2(0, n - 1);
  for (int i = 0; i < n; i++) { printf("%d ", nums[i]); }
  return 0;
}

✅ 优点 ​

  • 代码简洁，效率高。
  • 中间选 pivot 对有序/逆序数组表现良好。
  • 是经典且广泛使用的快排实现。

四、方法三：quickSort3 —— 三路快排（Three-way QuickSort） ​

重要：原始代码存在严重越界 Bug，以下为修正后的正确版本。

✅ 完整可运行代码 ​

cpp
#include <cstdio>
#include <iostream>
using namespace std;

const int N = 1e5 + 5;
int nums[N];

void quickSort3(int l, int r) {
  if (l >= r) return;
  // int x = nums[l + ((r - l) >> 1)];  // pivot 值
  int x = nums[l + rand() % (r - l + 1)];  // 随机生成位置取 pivot 值（推荐）
  int lt = l;                        // [l, lt-1] 为 < x 的区域
  int gt = r;                        // [gt+1, r] 为 > x 的区域
  int i = l;                         // 当前扫描指针

  while (i <= gt) {
    if (nums[i] < x) {
      swap(nums[i], nums[lt]);
      lt++;
      i++;
    } else if (nums[i] > x) {
      swap(nums[i], nums[gt]);
      gt--;
      // 注意：此处 i 不自增，因为从 gt 换来的元素未被检查
    } else {
      i++;  // 等于 x，直接跳过
    }
  }

  // 递归处理 < x 和 > x 的部分，== x 的部分已就位
  quickSort3(l, lt - 1);
  quickSort3(gt + 1, r);
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) { scanf("%d", &nums[i]); }
  quickSort3(0, n - 1);
  for (int i = 0; i < n; i++) { printf("%d ", nums[i]); }
  return 0;
}

五、方法四：quickSort4 —— 非递归实现（迭代版） ​

cpp
#include <cstdio>
#include <iostream>
#include <stack>
using namespace std;

const int N = 1e5 + 5;
int q[N];

void quickSort4(int q[], int l, int r) {
  // 1.
  // 边界条件判断：如果左边界大于等于右边界，说明区间无效或只有一个元素，无需排序
  if (l >= r) return;

  // 2. 使用栈来模拟递归调用过程，栈中交替存储待排序区间的 [左边界, 右边界]
  stack<int> stk;
  stk.push(l);
  stk.push(r);

  // 3. 只要栈不为空，就持续处理待排序区间
  while (!stk.empty())  // 修复了原代码中多余的 '3'，改为标准的 !stk.empty()
  {
    // 4. 弹出栈顶的右边界和左边界（注意：入栈是先左后右，所以出栈是先右后左）
    int rr = stk.top();
    stk.pop();
    int ll = stk.top();
    stk.pop();

    // 5. 防止无效区间入栈后造成的重复处理
    if (ll < rr) {
      // 6. Hoare 双指针分区初始化
      int i = ll - 1, j = rr + 1;
      // 随机选择一个基准值，避免最坏情况
      int x = q[ll + rand() % (rr - ll + 1)];

      // 7. 核心分区过程：将小于基准的放左边，大于基准的放右边
      while (i < j) {
        do { i++; } while (q[i] < x);
        do { j--; } while (q[j] > x);
        if (i < j) { swap(q[i], q[j]); }
      }

      // 8. 分区结束后，原区间被分为 [ll, j] 和 [j + 1, rr] 两部分
      // 将右半部分入栈（先入右，后入左，保证出栈时先处理左半部分，与递归顺序一致）
      stk.push(j + 1);
      stk.push(rr);

      // 将左半部分入栈
      stk.push(ll);
      stk.push(j);
    }
  }
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) { scanf("%d", &q[i]); }
  quickSort4(q, 0, n - 1);
  for (int i = 0; i < n; i++) { printf("%d ", q[i]); }
  return 0;
}

✅ 优势场景 ​

  • 输入包含大量重复元素（如 [5,5,5,1,5,9,5]）。
  • 时间复杂度可接近 O(n)。
  • 是处理“重复密集型”数据的最佳快排变种。

五、总结与使用建议 ​

方法适用场景是否推荐
quickSort1教学演示（展示随机化思想）❌ 不推荐（有缺陷）
quickSort2通用排序、竞赛、一般应用✅ 强烈推荐
quickSort3含大量重复元素的数据✅ 推荐

💡 最佳实践：

  • 日常使用 → quickSort2
  • 已知数据重复率高 → quickSort3（修正版）
  • 生产环境 → 直接使用 std::sort（基于 Introsort，更健壮）
最近更新