C语言快速排序算法通过基准值分区实现。初阶版本存在最坏时间复杂度O(N^2)问题，通过三数取中优化避免极值选取。高阶版本引入小区间切换堆排序减少递归开销。非递归版利用栈模拟递归过程防止栈溢出。文章涵盖霍夫曼分区、三数取中、小区间优化及非递归实现等核心变式。
快速排序有一个 key 值，叫基准元素，可以理解为就是要排序数组的第一个数字。在第一次快速排序结束后，这个 key 值位置发生改变，其他元素位置也发生一定改变。最后在 的左边都是小于 的数，在 的右边都是大于 的数。这就是一次快速排序，此时 的顺序就被排好了，后续也不需要动。
keykeykeykeykey然后，将整个数组以 key 分成两个左右两个区间，并在这两个区间循环刚刚的步骤，直到区间不可再分（区间只剩一个元素），此时排序结束。
一句话总结，快速排序就是不断将比 key 小的数放左边，把比 key 大的数放右边，最后完成排序。
第一步：定 key 值。快速排序有一个 key 值，叫基准元素，现在可以理解为就是第一个数字（后续还会再改进）。后续的排序就是围绕这个基准元素 key 来进行的。
第二步：大小交换。我们可以发现，视频中有两个小人，一个从左边往右走，一个从右往左走。先右小人一直向左走，直到遇到比 key 大的数停下；再左小人一直向右走，直到遇到比 key 小的数停下。当两小人都停下后，两小人所对应的值就互相交换，大的数换到右边，小的数换到左边。
第三步：循环。两小人继续一个左走，一个右走，满足条件时继续交换，然后重复。直到两小人相遇循环停止。
第四步：交换 key。此时将 key 与两小人相遇点的值进行交换。此时在 key 的左边都是小于 key 的数，在 key 的右边都是大于 key 的数。此时 key 就已经排好序，后续也不需要再动，第一轮快速排序结束。
第五步：分割区间。现在，key 就已经排好序，后续也不需要再动。此时将 key 左右的区间分割开来，分成左右两个区间。然后分别对这两个区间重复第一轮的排序：定 key 值、大小交换、循环、交换 key、分割区间。
第六步：结束。当每个区间分割成只剩下一个元素时，自然也不需要继续循环，就可以跳出循环。当所有的区间都只剩下一个元素时，都跳出循环时，排序也就完成了。
void QuickSort1(int* a, int left, int right) {
if (left >= right) // 判断是否继续，当区间只有一个数时跳出循环
return;
int key = left; // 确定 key 的值，为第一个元素
int L = left;
int R = right; // 先将左右的下标记录下来，以免后面丢失
while (left < right) { // 当左右小人相遇时就停止循环
while (left < right && a[right] >= a[key]) { // 右小人向左走，直到找到比 key 小的值
right--;
}
while (left < right && a[left] <= a[key]) { // 左小人向右走，直到找到比 key 大的值
left++;
}
Swap(&a[left], &a[right]); // 交换大的值和小的值
}
Swap(&a[right], &a[key]); // 最后交换 key 和相遇点对应的值
key = right; // key 的下标也要改变
QuickSort1(a, L, key - 1); // 递归 key 的左区间
QuickSort1(a, key + 1, R); // 递归 key 的右区间
}
在刚刚快速排序的初阶代码中，我们的 key 值是固定的，始终都是数组的第一项。但这样也会出现一些小问题。
若这个数组是完全有序的，会出现什么情况呢？首先，右小人先向左走，因为数组是有序的，找不到比第一个数 key 小的值，所以会一直走直到找到 key，且左右小人相遇（左小人起始位置为 key）。然后分割区间，key 单独一个区间，右边所有数一个区间，然后循环右区间。最后当排序结束时，发现每一次循环都只排好一个数，时间复杂度为 O(N^2)。
所以，当数组的顺序有序或几乎有序时，key 值就容易取到数组的极值，算法就很慢。
这里我们可以用三数取中的方法来解决取到极值。意思就是取数组的开头、中间、结尾三个数，数的大小在中间的就定为 key，可以一定程度上避免取到极值点。
// 三数取中，返回三个数的中间值
int FindKey(int* a, int left, int right) // 形参为数组以及左右两下标
{
int mid = (left + right) / 2; // 中间数的下标
if (a[left] > a[right]) {
if (a[right] > a[mid]) {
return right;
} else if (a[mid] > a[left]) {
return left;
} else {
return mid;
}
} else {
if (a[left] > a[mid]) {
return left;
} else if (a[mid] > a[right]) {
return right;
} else {
return mid;
}
}
}
void QuickSort1(int* a, int left, int right) {
if (left >= right) // 判断是否继续，当区间只有一个数时跳出循环
return;
int L = left;
int R = right; // 先将左右的下标记录下来，以免后面丢失
int key = FindKey(a, left, right);
Swap(&a[key], &a[left]); key = left;
while (left < right) { // 当左右小人相遇时就停止循环
while (left < right && a[right] >= a[key]) { // 右小人向左走，直到找到比 key 小的值
right--;
}
while (left < right && a[left] <= a[key]) { // 左小人向右走，直到找到比 key 大的值
left++;
}
Swap(&a[left], &a[right]); // 交换大的值和小的值
}
Swap(&a[right], &a[key]); // 最后交换 key 和相遇点对应的值
key = right; // key 的下标也要改变
QuickSort1(a, L, key - 1); // 递归 key 的左区间
QuickSort1(a, key + 1, R); // 递归 key 的右区间
}
由于我们的快速排序是由递归实现的，每递归一次就多一半的区间，最后的区间数是 2^n ( n 为递归次数 )。而在第倒数 1、2 个递归时，区间内只有几个数，这时候用之前的办法就效率不高，且还会多两倍的区间。所以，我们可以当区间内个数少于一定时，采用其他排序，这样就可以减少大量的递归，提高效率。
当区间个数小于 10 时，就采用堆排序，可以有效的提高效率。
// 三数取中，返回三个数的中间值
int FindKey(int* a, int left, int right) {
int mid = (left + right) / 2; // 中间数的下标
if (a[left] > a[right]) {
if (a[right] > a[mid]) {
return right;
} else if (a[mid] > a[left]) {
return left;
} else {
return mid;
}
} else {
if (a[left] > a[mid]) {
return left;
} else if (a[mid] > a[right]) {
return right;
} else {
return mid;
}
}
}
// 快速排序递归实现
// 快速排序 hoare 版本
int PartSort1(int* a, int left, int right) {
int key = FindKey(a, left, right); // 找到中间下标并给 key
Swap(&a[key], &a[left]); key = left; // 将 key 位置换到首项
while (left < right) { // 当左右小人相遇时就停止循环
while (left < right && a[right] >= a[key]) { // 右小人向左走，直到找到比 key 小的值
right--;
}
while (left < right && a[left] <= a[key]) { // 左小人向右走，直到找到比 key 大的值
left++;
}
Swap(&a[left], &a[right]); // 交换大的值和小的值
}
Swap(&a[right], &a[key]); // 最后交换 key 和相遇点对应的值
return right; // 返回最后 key 的下标，方便分割
}
// 插入排序
void InsertSort(int* a, int n) {
// [0, n-1]
for (int i = 0; i < n - 1; i++) {
// [0, n-2] 是最后一组
// [0,end] 有序 end+1 位置的值插入 [0,end]，保持有序
int end = i;
int tmp = a[end + 1];
while (end >= 0) {
if (tmp < a[end]) { a[end + 1] = a[end]; --end; }
else { break; }
}
a[end + 1] = tmp;
}
}
// 将交换的元素向下调整
void AdJustDown(int* a, int parent, int size) {
// 先假设左孩子小
int child = 2 * parent + 1;
while (child <= size - 1) {
if (child + 1 <= size - 1 && a[child + 1] > a[child]) { child++; }
if (a[child] > a[parent]) {
Swap(&a[child], &a[parent]); parent = child; child = 2 * parent + 1;
} else { break; }
}
}
// 堆排序
void HeapSort(int* a, int sz) {
int i;
for (i = (sz - 1 - 1) / 2; i >= 0; i--) {
AdJustDown(a, i, sz);
}
for (i = sz - 1; i > 0; i--) {
Swap(&a[0], &a[i]);
AdJustDown(a, 0, i);
}
}
void QuickSort1(int* a, int left, int right) {
if (left >= right) // 判断是否继续，当区间只有一个数时跳出循环
return;
int g = right - left + 1;
if (g < 10) {
HeapSort(a + left, g); // 堆排序
} else {
int key = PartSort1(a, left, right); // 接收返回值
QuickSort1(a, left, key - 1); // 递归 key 的左区间
QuickSort1(a, key + 1, right); // 递归 key 的右区间
}
}
在我们进行递归的快速排序时，若数据量过大，就会递归很多次，可能会出现栈溢出。为了避免出现这种情况，我们可以采用非递归的方式解决。
我们可以使用一个栈来实现。将区间的左、右范围分别存在栈中，当取出一个区间后，就存下这个区间的两个分割区间（前提是区间存在）。当栈为空且不能再存入时，排序就好了。
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <sperror.h> // 重定义，方便修改类型
typedef int STDataType; // 定义栈
typedef struct Stack {
STDataType* a; // 数组指针
int size; // 总元素
int capacity; // 容量
} Stack;
// 初始化栈 void StackInit(Stack* ps);
// 入栈 void StackPush(Stack* ps, STDataType data);
// 出栈 void StackPop(Stack* ps);
// 获取栈顶元素 STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回 0 int StackEmpty(Stack* ps);
// 销毁栈 void StackDestroy(Stack* ps);
#include "Stack.h"
// 初始化栈
void StackInit(Stack* ps) {
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->size = 0; // 全部初始化置 0 / NULL
}
// 入栈
void StackPush(Stack* ps, STDataType data) {
assert(ps); // 断言空指针
if (ps->size == ps->capacity) { // 当 size=capacity 时就表示空间不足，此时需要增容，故进入 if 语句
// 先设置新变量，增容后再赋值
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; // 设置一个三目操作符判断原空间是否为 0
// 当原空间为 0 时给空间开辟 4 字节；当原空间不为 0 时给空间增容 2 倍
STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType)); // 由于是在原空间的基础上给空间增容，故我们这里使用 realloc 函数 增容
// 增容大小为上面的 newcapacity *（类型大小）
if (tmp == NULL) { // 加一个 if 语句 防止增容失败
perror("realloc");
return;
}
// 没有问题后就赋值
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->size] = data;
ps->size++;
}
// 出栈
void StackPop(Stack* ps) {
assert(ps && ps->size > 0); // 断言空指针
// 断言顺序表不能为空
ps->size--; // 将元素个数进行 -1 就行
// 这样也不会影响到后面的 增、删、查、改
}
// 获取栈顶元素
STDataType StackTop(Stack* ps) {
assert(ps && ps->size > 0); // 断言空指针
// 断言顺序表不能为空
return ps->a[ps->size - 1];
}
// 获取栈中有效元素个数
int StackSize(Stack* ps) {
assert(ps); // 断言空指针
return ps->size;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回 0
int StackEmpty(Stack* ps) {
assert(ps); // 断言空指针
return ps->size == 0;
}
// 销毁栈
void StackDestroy(Stack* ps) {
assert(ps); // 断言空指针
free(ps->a); // 释放内存
ps->a = NULL;
ps->capacity = 0;
ps->size = 0; // 全部初始化置 0 / NULL
}
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right) {
Stack S;
StackInit(&S);
// 首次添加数据
StackPush(&S, right);
StackPush(&S, left);
// 当栈不为空时循环
while (!StackEmpty(&S)) {
int L = StackTop(&S);
StackPop(&S);
int R = StackTop(&S);
StackPop(&S);
// 取出值并从栈删除
if (L >= R) {
return;
}
// 小区间优化
int g = R - L + 1;
if (g < 10) {
// 堆排序
HeapSort(a + L, g);
} else {
int key = PartSort1(a, L, R); // 没越界就插入新数据
if (R - key - 1 > 1) {
StackPush(&S, R);
StackPush(&S, key + 1);
}
if (key - 1 - L > 1) {
StackPush(&S, key - 1);
StackPush(&S, L);
}
}
}
// 最后销毁
StackDestroy(&S);
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online