深入理解快速排序：从数组到链表，递归与非递归全解析

快速排序作为十大经典排序算法之一是实际开发中应用最广泛的排序算法平均时间复杂度为 O(nlogn)空间复杂度为 O(logn)核心思想是分治法通过一趟排序将待排序列分割成独立的两部分其中一部分元素均比基准值小另一部分均比基准值大再递归对两部分排序最终整体有序。本文基于 C 实现快速排序的多种核心版本数组递归 / 非递归、链表快排并拓展快排的经典应用查找第 K 小元素、最大两值逐行解析代码逻辑带你彻底吃透快排一、前置知识与工具函数所有代码基于 C 实现包含基础的打印、断言校验工具函数统一复用#includestdio.h #includeiostream #includeassert.h #includestdlib.h #includestring.h #includestack #includequeue using namespace std; // 打印数组 void printAr(const int* ar, int n) { assert(ar ! nullptr); for (int i 0; i n; i) { printf(%5d, ar[i]); } printf(\n--------------------\n); }二、数组快速排序核心基础数组快排的核心是划分函数Partition将数组按基准值分割本文实现两种划分方式 递归 / 非递归排序。1. 双向划分经典 Partition以左边界为基准值左右双指针遍历交换不符合条件的元素最终将基准值放到正确位置// 双向划分快排核心 int Partition(int* ar, int left, int right) { assert(ar ! nullptr); int i left, j right; int tmp ar[i]; // 选取左边界为基准 while (i j) { // 右指针向左找小于基准的元素 while (i j ar[j] tmp) --j; ar[i] ar[j]; // 左指针向右找大于基准的元素 while (i j ar[i] tmp) i; ar[j] ar[i]; } ar[i] tmp; // 基准值归位 return i; // 返回基准下标 }2. 单向划分简洁版 Partition单指针遍历将小于基准的元素交换到左侧逻辑更简单适合新手理解// 单向划分 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; swap(ar[i], ar[j]); } } swap(ar[left], ar[i]); // 基准归位 return i; }3. 递归版快排分治法思想划分后递归处理左、右子数组// 递归快排核心 void RecQSort(int* ar, int left, int right) { if (left right) { int mid Partition(ar, left, right); // 划分 RecQSort(ar, left, mid - 1); // 递归左区间 RecQSort(ar, mid 1, right); // 递归右区间 } } // 递归快排入口 void QuickSort(int* ar, int n) { assert(ar ! nullptr); if (n 2)return; // 边界元素2无需排序 RecQSort(ar, 0, n - 1); }4. 非递归版快排递归本质是函数调用栈非递归版用队列 / 栈模拟递归过程避免栈溢出// 非递归快排队列实现 void NiceQuickSort(int* ar, int n) { assert(ar ! nullptr); if (n 2)return; int left 0, right n - 1; queueint qu; qu.push(left); qu.push(right); while (!qu.empty()) { // 取出待排序区间 left qu.front(); qu.pop(); 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); } } }5. 数组快排测试int main() { int ar[] { 56,12,90,89,23,34,100,67,45,78,56 }; int n sizeof(ar) / sizeof(ar[0]); printAr(ar, n); // QuickSort(ar, n); // 递归版 NiceQuickSort(ar, n); // 非递归版 printAr(ar, n); return 0; }运行结果56 12 90 89 23 34 100 67 45 78 56 -------------------- 12 23 34 45 56 56 67 78 89 90 100 --------------------三、链表快速排序进阶数组支持随机访问链表只能顺序遍历因此快排划分需基于指针遍历核心逻辑与数组单向划分一致1. 链表结构定义 工具函数// 链表节点定义 typedef struct ListNode { int data; struct ListNode* next; }ListNode,*LinkList; // 打印链表 void PrintList(ListNode* head) { ListNode* p head; while (p ! nullptr) { printf(%5d, p-data); p p-next; } printf(\n----------------\n); } // 创建节点 ListNode* Buynode() { ListNode* s (ListNode*)malloc(sizeof(ListNode)); if (nullptr s)exit(EXIT_FAILURE); memset(s, 0, sizeof(ListNode)); return s; } // 头插法创建链表 ListNode* Push_Front(ListNode* head, int val) { ListNode* s Buynode(); s-data val; s-next head; head s; return head; }2. 链表快排核心实现// 链表划分单向划分 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; swap(i-data, j-data); } } swap(left-data, i-data); // 基准归位 return i; } // 递归链表快排 void LQSort(ListNode* left, ListNode* right) { if (left ! right) { ListNode* mid ListPartition(left, right); // 划分 LQSort(left, mid); // 递归左区间 LQSort(mid-next, right); // 递归右区间 } } // 链表快排入口 void LinkQuickSort(ListNode* head) { LQSort(head, nullptr); }3. 链表快排测试int main() { LinkList head nullptr; int ar[] { 56,12,90,89,23,34,100,67,45,78,56 }; int n sizeof(ar) / sizeof(ar[0]); // 头插法构建链表 for (int i 0; i n; i) { head Push_Front(head, ar[i]); } PrintList(head); LinkQuickSort(head); // 链表快排 PrintList(head); return 0; }运行结果与数组快排一致链表实现有序排序。四、快速排序经典应用面试高频快排的划分思想能高效解决查找第 K 小 / 大元素、最大两值等问题时间复杂度远低于全排序。1. 查找数组中最大的两个值一次遍历即可完成无需排序// 查找最大的两个值 void Print2Max(int* ar, int n) { assert(ar ! nullptr); if (n 2)return; int max1 max(ar[0], ar[1]); // 最大值 int max2 min(ar[0], ar[1]); // 次大值 for (int i 2; i n; i) { if (ar[i] max1) { max2 max1; max1 ar[i]; } else if (ar[i] max2) { max2 ar[i]; } } printf(max1:%5d max2:%5d\n, max1, max2); }2. 查找第 K 小元素快排划分优化利用划分函数仅递归包含 K 的区间无需全排序时间复杂度 O(n)// 查找第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 j pos - left 1; // 左区间元素个数 if (k j)return SelectKM(ar, left, pos, k); // K在左区间 else return SelectKM(ar, pos 1, right, k - j); // K在右区间 } // 第K小元素入口 int SelectKMin(int* ar, int n, int k) { assert(ar ! nullptr); if (n 1 || k1 || kn)return -1; return SelectKM(ar, 0, n - 1, k); }3. 应用测试int main() { int ar[] { 56,12,90,89,23,34,100,67,45,78 }; int n sizeof(ar) / sizeof(ar[0]); printAr(ar, n); // 测试第K小 for (int k 1; k n; k) { int kmin SelectKMin(ar, n, k); printf(第%d小元素%d\n, k, kmin); } // 测试最大两值 Print2Max(ar, n); printAr(ar, n); return 0; }五、关键知识点总结快排核心划分函数Partition将数组 / 链表按基准值分割为两部分两种划分双向划分效率高、单向划分易理解两种实现递归代码简洁、非递归避免栈溢出链表适配基于指针遍历实现单向划分不支持随机访问核心优势平均时间复杂度 O(nlogn)原地排序应用广泛面试考点第 K 小元素、非递归实现、链表快排。六、完整代码整合本文所有代码已分模块实现可直接复制编译运行建议手动敲一遍代码加深对快排分治思想的理解