概述
快速排序是 C 语言库中常用的高效排序算法。本文将介绍从基础到高阶的快速排序实现，包括多种优化策略。
C算法
C 语言快速排序算法详解与优化实现
详细讲解了 C 语言中的快速排序算法，包含基础 Hoare 版本实现、三数取中优化、小区间优化以及非递归实现方案。文章通过代码示例展示了如何避免最坏情况下的性能退化，并利用堆排序优化小数据量区间的效率，同时提供了基于栈的非递归实现以避免栈溢出问题。
详细讲解了 C 语言中的快速排序算法，包含基础 Hoare 版本实现、三数取中优化、小区间优化以及非递归实现方案。文章通过代码示例展示了如何避免最坏情况下的性能退化，并利用堆排序优化小数据量区间的效率，同时提供了基于栈的非递归实现以避免栈溢出问题。
快速排序是 C 语言库中常用的高效排序算法。本文将介绍从基础到高阶的快速排序实现，包括多种优化策略。
快速排序有一个基准元素（key），通常选择数组的第一个数字。排序结束后，key 左边的数都小于它，右边的数都大于它。然后以 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>
// 重定义，方便修改类型
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);
}
本文详细介绍了 C 语言中的快速排序算法及其优化方案，涵盖了从基础递归实现到非递归实现的完整流程。通过三数取中和小区间优化等手段，有效提升了算法在不同数据分布下的性能表现。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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