当前位置：首页 > news >正文

【C++实现】快速排序（递归+非递归+链表+TopK）从原理到源码详解

news 2026/3/26 23:55:16

前言

快速排序（Quick Sort）是C/C++ 工程开发与面试中的绝对王者。它不仅平均时间复杂度达到了O(nlogn)，在实际运行中往往比同复杂度的堆排序、归并排序更快（缓存命中率高）。

今天，我将基于一段可直接运行的 C 语言源码，带你全方位拆解快速排序。这篇文章不仅包含标准的数组递归 / 非递归实现，还涵盖了链表快排和 **TopK（第 K 小）** 问题的变形，代码逻辑清晰，适合考研与校招面试背诵。

一、快速排序核心思想：分治（Divide & Conquer）

快速排序的核心逻辑只有三步：

选基准（Pivot）：从数组中选出一个元素作为基准。
划分（Partition）：重新排列数组，将所有比基准小的放左边，比基准大的放右边（基准最终处于中间位置）。
递归：分别递归地对左右两个子数组重复上述过程。

关键点：

原地排序：不需要额外的数组空间。
不稳定：相等元素的相对位置可能改变。

二、核心代码详解：三种划分方式

1. 左右指针划分（经典双路快排）

逻辑：设置左右两个指针，左指针找比基准大的数，右指针找比基准小的数，交换，直到相遇。

适用：常规数组排序，效率较高。

#include <stdio.h> #include <stdlib.h> #include <assert.h> #include<queue> #include<string> // 打印数组（辅助函数） void PrintAr(const int* ar, int n) { assert(ar != nullptr); for (int i = 0; i < n; ++i) { printf("%5d", ar[i]); } printf("\n--------------------------------\n"); } // 左右指针划分（标准划分） int Partition(int* ar, int left, int right) { assert(ar != nullptr); int i = left; int j = right; // 基准选左边第一个 int tmp = ar[i]; while (i < j) { // 从右往左找，小于基准的数 while (i < j && tmp < ar[j]) --j; ar[i] = ar[j]; // 填坑 // 从左往右找，大于等于基准的数 while (i < j && tmp >= ar[i]) ++i; ar[j] = ar[i]; // 填坑 } ar[i] = tmp; // 基准归位 return i; // 返回基准下标 }

2. 随机基准划分

逻辑：为了防止在有序数组下退化成 O (n²)，随机选择一个元素与基准交换。

适用：处理极端有序数据。

// 随机划分优化 int RandPartition(int* ar, int left, int right) { assert(ar != nullptr); // 随机生成一个位置 int pos = rand() % (right - left + 1) + left; // 交换到最左边，复用 Partition 逻辑 std::swap(ar[left], ar[pos]); return Partition(ar, left, right); }

3. 单向划分（简单易写，链表通用）

逻辑：只用一个指针扫描，将小于基准的数交换到左侧区间。

优点：代码量最小，且是链表快排的唯一实现方式。

// 单向划分（最简单） int UniPartition(int* ar, int left, int right) { assert(ar != nullptr && left < right); if (left == right) return left; int i = left; // 标记"小于基准区"的最后边界 int j = left + 1; // 遍历指针 int tmp = ar[left]; // 基准 for (; j <= right; ++j) { // 遇到比基准小的，推进边界并交换 if (tmp >= ar[j]) { i += 1; std::swap(ar[i], ar[j]); } } // 最后把基准换到 i 位置 std::swap(ar[left], ar[i]); return i; }

三、数组快速排序（递归版）

// 递归排序核心 void RecQSort(int* ar, int left, int right) { if (left < right) // 递归终止条件：区间内只有一个元素 { // 1. 划分区间，找到基准位置 int mid = UniPartition(ar, left, right); // 2. 递归排序左区间 RecQSort(ar, left, mid - 1); // 3. 递归排序右区间 RecQSort(ar, mid + 1, right); } } // 对外接口函数 void QuickSort(int* ar, int n) { assert(ar != nullptr); if (n < 2) return; // 小于2个元素无需排序 RecQSort(ar, 0, n - 1); }

四、非递归快速排序（用队列模拟）

为什么需要非递归？

当数据量极大（如 100 万条）时，递归深度过深可能导致栈溢出（Stack Overflow）。

我们可以用 ** 队列（Queue）** 来模拟递归过程，保存待排序的区间。

// 非递归快排（使用队列模拟递归） void NiceQuickSort(int* ar, int n) { assert(ar != nullptr); if (n < 2) return; std::queue<int> qu; // 初始区间入队 qu.push(0); qu.push(n - 1); while (!qu.empty()) { // 出队获取当前区间 int left = qu.front(); qu.pop(); int right = qu.front(); qu.pop(); // 划分 int mid = Partition(ar, left, right); // 左区间有效，入队 if (left < mid - 1) { qu.push(left); qu.push(mid - 1); } // 右区间有效，入队 if (mid + 1 < right) { qu.push(mid + 1); qu.push(right); } } }

五、进阶应用：单链表快速排序

链表快排不能像数组那样随机访问，所以只能使用单向划分。

// 单链表节点定义 typedef struct ListNode { int data; struct ListNode* next; } ListNode, * LinkList; // 链表划分（同数组单向划分逻辑） ListNode* ListPartition(ListNode* left, ListNode* right) { if (left == nullptr || left == right) return left; ListNode* i = left; ListNode* j = left->next; int tmp = left->data; for (; j != right; j = j->next) { if (tmp >= j->data) { i = i->next; std::swap(i->data, j->data); } } std::swap(left->data, i->data); return i; } // 链表递归排序 void LQSort(ListNode* left, ListNode* right) { if (left != right) // 注意终止条件：left == right 时只有一个节点 { ListNode* mid = ListPartition(left, right); LQSort(left, mid); LQSort(mid->next, right); } } // 链表排序接口 void LinkQuickSort(ListNode* head) { LQSort(head, nullptr); }

六、面试必刷题：寻找第 K 小（TopK）

利用快速排序的划分思想，我们可以在O(n)的平均时间复杂度内求出第 K 小元素。

// 寻找第 K 小（递归） int SelectKM(int* ar, int left, int right, int k) { if (left == right && k == 1) return ar[left]; int pos = Partition(ar, left, right); // 计算基准左边有多少个数（含基准） int distance = pos - left + 1; if (k <= distance) { // 第 K 小在左边 return SelectKM(ar, left, pos, k); } else { // 第 K 小在右边，偏移 K 的值 return SelectKM(ar, pos + 1, right, k - distance); } } // 封装函数 int SelectKMin(int* ar, int n, int k) { assert(ar != nullptr); if (n < 1 || k < 1 || k > n) return -1; // 非法输入 return SelectKM(ar, 0, n - 1, k); }

七、完整测试代码（Main 函数）

int main() { int ar[] = { 56, 12, 90, 89, 23, 34, 100, 67, 45, 78 }; int n = sizeof(ar) / sizeof(ar[0]); printf("排序前：\n"); PrintAr(ar, n); // 测试数组快排 // QuickSort(ar, n); // 测试非递归快排 // NiceQuickSort(ar, n); printf("排序后：\n"); PrintAr(ar, n); // 测试第 K 小 printf("\n=== 测试第 K 小 ===\n"); for (int k = 1; k <= n; ++k) { int kmin = SelectKMin(ar, n, k); printf("k: %d => val : %d \n", k, kmin); } return 0; }