本文详细介绍了多种经典排序算法的原理与 C 语言实现。内容包括直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序、快速排序（Hoare、挖坑法、前后指针法及非递归实现）、归并排序以及计数排序。文章通过代码示例展示了各算法的核心逻辑，如建堆、分治策略、空间换时间等思想，适合学习数据结构与算法基础。
end 初始指向已排序部分的最后一个下标，end+1 初始为待排序数据。我们将 end+1 的数据暂存到 tmp 变量中。
tmp 与 end 位置的数据比较，若 end 比 tmp 大，则将 end 的数据放到 end+1 位置上，并让 end--，在已排好序的数组中寻找合适位置；反之则将 tmp 数据放到 end+1 的位置。
// 直接插入排序
void InsertSort(int* arr, int num) {
for (int i = 0; i < num - 1; i++) {
int end = i;
int tmp = arr[end + 1];
while (end >= 0) {
if (arr[end] > tmp)
arr[end + 1] = arr[end];
else
break;
end--;
}
arr[end + 1] = tmp;
}
}
该算法属于插入排序的优化版本。
首先明确，直接插入排序为何时间复杂度较高？
最坏情况下，若数组倒序，每次插入都需要调整到已排序部分的最前面。若能减少调整次数，效率将提升。
若先将数组调整为只需少量调整的预排序状态，可解决逐个查找的问题。通过设置间隔变量 gap（如 num/3+1）进行大步长调整，之后逐渐减小 gap，直至 gap 为 1 时执行完整插入排序。
基于插入排序修改：
for (int i = 0; i < num - gap; i++) {
int end = i;
int tmp = arr[end + gap];
while (end >= 0) {
if (arr[end] > tmp)
arr[end + gap] = arr[end];
else
break;
end -= gap;
}
arr[end + gap] = tmp;
}
外层循环控制 gap 变化：
void ShellSort(int* arr, int num) {
int gap = num;
while (gap > 1) {
gap = gap / 3 + 1;
for (int i = 0; i < num - gap; i++) {
int end = i;
int tmp = arr[end + gap];
while (end >= 0) {
if (arr[end] > tmp)
arr[end + gap] = arr[end];
else
break;
end -= gap;
}
arr[end + gap] = tmp;
}
}
}
先给 gap 赋值为数组长度，确保循环内部修改后 gap 为 1 时能执行一次。
遍历数组查找最小值，与已排序末尾交换。
遍历效率较低，能否一次循环找最大和最小两个值？
使用 begin 和 end 分别指向待排序数组的头尾，将找到的最小值和最大值与 begin 和 end 交换。中间为未排序部分，两边为已排序部分。用 maxi 和 mini 记录最大和最小值的下标。
内层逻辑：
int mini = begin;
int maxi = end;
for (int i = begin; i <= end; i++) {
if (arr[i] > arr[maxi]) maxi = i;
if (arr[i] < arr[mini]) mini = i;
}
if (maxi == begin) maxi = mini;
Swap(&arr[begin], &arr[mini]);
Swap(&arr[end], &arr[maxi]);
begin++;
end--;
增加判断是为了避免当 maxi 位于 begin 位置时，第一次交换导致数据错位的问题。
完整函数：
void SelectSort(int* arr, int num) {
int begin = 0;
int end = num - 1;
while (begin < end) {
int mini = begin;
int maxi = end;
for (int i = begin; i <= end; i++) {
if (arr[i] > arr[maxi]) maxi = i;
if (arr[i] < arr[mini]) mini = i;
}
if (maxi == begin) maxi = mini;
Swap(&arr[begin], &arr[mini]);
Swap(&arr[end], &arr[maxi]);
begin++;
end--;
}
}
基于堆结构，通过建堆、将堆顶换至末位、维护堆完成排序。
核心在于维护堆和建堆。
建堆可使用向下调整算法，找到最后一个父节点：parent = (num - 2) / 2。
维护堆类似出栈，栈顶与栈尾交换，对栈顶使用向下调整算法。
递增序列应建大堆还是小堆？
建大堆，使最大数据优先放到数组末尾。
向下调整算法：
// 向下调整算法
void AdjustDown(int* arr, int parent, int size) {
int child = parent * 2 + 1;
while (child < size) {
// 大堆：找最大的子节点
if (child + 1 < size && arr[child] < arr[child + 1])
child++;
if (arr[parent] < arr[child])
Swap(&arr[parent], &arr[child]);
else
break;
parent = child;
child = parent * 2 + 1;
}
}
堆排序算法：
// 堆排序
void HeapSort(int* arr, int num) {
// 建堆
for (int i = (num - 2) / 2; i >= 0; i--) {
AdjustDown(arr, i, num);
}
// 堆排序
for (int i = num - 1; i > 0; i--) {
Swap(&arr[0], &arr[i]);
AdjustDown(arr, 0, i);
}
}
相邻元素比较，大的往后放，每轮确定一个最大值。
// 冒泡排序
void BubbleSort(int* arr, int num) {
for (int i = 0; i < num - 1; i++) {
for (int j = 0; j < num - i - 1; j++) {
if (arr[j] > arr[j + 1])
Swap(&arr[j], &arr[j + 1]);
}
}
}
选取基准值 key，小于 key 的放左边，大于 key 的放右边。
left 从右往左找小于 key 的值，right 从左往右找大于 key 的值，交换后继续，直到 right < left。
// Hoare 版本
int _QuickSort(int* arr, int left, int right) {
int keyi = left;
left++;
while (left <= right) {
while (arr[right] >= arr[keyi] && left < right)
right--;
while (arr[left] <= arr[keyi] && left < right)
left++;
if (left <= right)
Swap(&arr[left++], &arr[right--]);
}
Swap(&arr[keyi], &arr[right]);
return right;
}
递归代码：
// 快速排序
void QuickSort(int* arr, int left, int right) {
if (left >= right)
return;
int keyi = _QuickSort(arr, left, right);
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}
第一个数据放入坑中，left 位置产生坑，right 先走找小于 key 的值填入左边坑，随后 left 走找大于 key 的值填入右边坑，循环至 right < left，最后填入 key。
// 挖坑法
int _QuickSort_hole(int* arr, int left, int right) {
int hole = left;
int key = arr[hole];
while (left < right) {
while (arr[right] >= key && left < right)
right--;
arr[hole] = arr[right];
hole = right;
while (arr[left] <= key && left < right)
left++;
arr[hole] = arr[left];
hole = left;
}
arr[hole] = key;
return hole;
}
prev 存放已找到的比 key 小的数据，cur 寻找比 key 小的数据，找到则与 prev+1 交换。遍历完后 prev 与 key 交换。
// Lomuto 前后指针
int _QuickSort_lomuto(int* arr, int left, int right) {
int keyi = left;
int prev = left;
int cur = left + 1;
while (cur <= right) {
if (arr[cur] < arr[keyi] && ++prev != cur)
Swap(&arr[prev], &arr[cur]);
cur++;
}
Swap(&arr[keyi], &arr[prev]);
return prev;
}
借助栈代替递归，保存左右边界参数。
// 非递归版本快速排序——借助栈
void QuickSortNoR(int* arr, int left, int right) {
ST st;
StackInit(&st);
StackPush(&st, left);
StackPush(&st, right);
while (!STEmpty(&st)) {
int end = StackTop(&st);
StackPop(&st);
int start = StackTop(&st);
StackPop(&st);
int keyi = _QuickSort_lomuto(arr, start, end);
if (start < keyi - 1) {
StackPush(&st, start);
StackPush(&st, keyi - 1);
}
if (end > keyi + 1) {
StackPush(&st, keyi + 1);
StackPush(&st, end);
}
}
StackDestory(&st);
}
递归将数组拆分至单个数据，回档时合并有序序列。
void _MergeSort(int* arr, int left, int right, int* tmp) {
if (left >= right)
return;
int mid = (left + right) / 2;
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid + 1, right, tmp);
// 合并两个有序的序列
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int i = begin1;
while (begin1 <= end1 && begin2 <= end2) {
if (arr[begin1] < arr[begin2])
tmp[i++] = arr[begin1++];
else
tmp[i++] = arr[begin2++];
}
while (begin1 <= end1)
tmp[i++] = arr[begin1++];
while (begin2 <= end2)
tmp[i++] = arr[begin2++];
memmove(arr + left, tmp + left, (right - left + 1) * sizeof(int));
}
// 归并排序
void MergeSort(int* arr, int num) {
int* tmp = (int*)malloc(num * sizeof(int));
if (tmp == NULL) {
perror("MergeSort::malloc");
exit(1);
}
_MergeSort(arr, 0, num - 1, tmp);
free(tmp);
}
通过数组记录每个数据的个数，再根据计数表还原数据。
// 计数排序
void CountSort(int* arr, int num) {
int min = arr[0];
int max = arr[0];
// 获取当前数据的偏移量
for (int i = 0; i < num; i++) {
if (arr[i] < min)
min = arr[i];
if (arr[i] > max)
max = arr[i];
}
int range = max - min + 1;
int* count = (int*)calloc(range, sizeof(int));
if (count == NULL) {
perror("CountSort::malloc");
exit(1);
}
// 将数据放到计数表中
for (int i = 0; i < num; i++) {
count[arr[i] - min]++;
}
// 将数据放到原数组当中
int index = 0;
for (int i = 0; i < range; i++) {
while (count[i]--)
arr[index++] = i + min;
}
free(count);
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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