C 语言排序算法全解析：从原理到实战，附性能对比

排序是计算机科学中最基础且核心的操作之一，它通过特定规则将无序数据转化为有序序列，广泛应用于购物筛选、数据统计、院校排名等实际场景。在 C 语言中，排序算法的实现直接影响程序的执行效率，不同场景下选择合适的排序算法能显著提升性能。本文将详细拆解常见排序算法的原理、代码实现，并通过实战对比分析各算法的优劣，帮助读者深入理解并灵活运用。

一、排序基础概念

1.1 核心定义

排序：使一串记录按照某个或某些关键字的大小，递增或递减排列的操作。关键字可以是数字、字符等可比较的属性，例如商品价格、销量、学生成绩等。

1.2 关键评价指标

• 时间复杂度：算法执行所需的时间与数据规模的关系，反映算法的执行效率。
• 空间复杂度：算法执行所需的额外存储空间与数据规模的关系。
• 稳定性：若待排序序列中存在多个关键字相同的记录，排序后它们的相对次序保持不变，则称该算法稳定；否则不稳定。稳定性在多关键字排序场景（如先按价格排序，再按销量排序）中至关重要。

1.3 常见排序算法分类

根据实现思路，常见排序算法可分为以下几类：

• 插入排序：直接插入排序、希尔排序
• 选择排序：直接选择排序、堆排序
• 交换排序：冒泡排序、快速排序
• 归并排序：二路归并排序
• 非比较排序：计数排序

二、经典排序算法详解（原理 + 代码）

以下所有算法均基于整型数组排序（升序）实现，测试用例统一为：int a[] = {5, 3, 9, 6, 2, 4, 7, 1, 8}

2.1 插入排序类

插入排序的核心思想是：将待排序元素逐个插入到已有序的子序列中，最终形成完整的有序序列。

2.1.1 直接插入排序

原理：

• 初始时，将第一个元素视为有序子序列。
• 对于第 i（i≥1）个元素，与有序子序列中的元素从后往前依次比较。
• 找到合适的插入位置，将该元素插入，原位置元素依次后移。

这就像玩扑克牌时，我们会把新摸到的牌插入到手中已排好序的牌组中。

代码实现：

#include <stdio.h> // 直接插入排序（升序） void InsertSort(int* a, int n) { // 遍历待插入的元素（从第二个元素开始） for (int i = 0; i < n - 1; i++) { int end = i; // 有序子序列的最后一个元素下标 int tmp = a[end + 1]; // 待插入的元素 // 从后往前查找插入位置 while (end >= 0) { if (a[end] > tmp) { a[end + 1] = a[end]; // 元素后移 end--; } else { break; // 找到插入位置，退出循环 } } a[end + 1] = tmp; // 插入元素 } } // 打印数组 void PrintArray(int* a, int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } int main() { int a[] = {5, 3, 9, 6, 2, 4, 7, 1, 8}; int n = sizeof(a) / sizeof(a[0]); printf("直接插入排序前："); PrintArray(a, n); InsertSort(a, n); printf("直接插入排序后："); PrintArray(a, n); return 0; }

特性总结：

• 时间复杂度：O (N²)（最坏 / 平均情况），O (N)（最好情况，数组已有序）
• 空间复杂度：O (1)（原地排序）
• 稳定性：稳定
• 适用场景：数据量小或接近有序的场景（如少量数据的局部排序）

2.1.2 希尔排序（缩小增量排序）

原理：直接插入排序在数据量较大且无序时效率较低，希尔排序通过 "预排序" 让数组接近有序，再进行直接插入排序，从而优化性能。

• 选定一个增量 gap（初始通常为 n/3+1），将数组按 gap 分组，每组内元素距离为 gap。
• 对每组内元素进行直接插入排序。
• 缩小 gap（gap=gap/3+1），重复分组和排序操作。
• 当 gap=1 时，数组已接近有序，此时进行一次直接插入排序即可完成最终排序。

代码实现：

// 希尔排序（升序） void ShellSort(int* a, int n) { int gap = n; // 逐步缩小gap，直到gap=1 while (gap > 1) { gap = gap / 3 + 1; // 增量计算公式，确保最后gap=1 // 对每组进行插入排序 for (int i = 0; i < n - gap; i++) { int end = i; int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } } int main() { int a[] = {5, 3, 9, 6, 2, 4, 7, 1, 8}; int n = sizeof(a) / sizeof(a[0]); printf("希尔排序前："); PrintArray(a, n); ShellSort(a, n); printf("希尔排序后："); PrintArray(a, n); return 0; }

特性总结：

• 时间复杂度：O (N^1.3)~O (N²)（取决于 gap 序列，严蔚敏《数据结构》中给出平均复杂度约 O (N^1.3)）
• 空间复杂度：O (1)
• 稳定性：不稳定（分组排序会破坏相同元素的相对次序）
• 适用场景：中等数据量的排序，性能优于直接插入排序

2.2 选择排序类

选择排序的核心思想是：每次从待排序序列中选出最小（或最大）的元素，放到序列的起始（或末尾）位置，重复直到排序完成。

2.2.1 直接选择排序

原理：

• 遍历序列，找到最小元素和最大元素的下标。
• 将最小元素与序列起始位置元素交换，最大元素与序列末尾位置元素交换。
• 缩小排序范围（起始位置后移，末尾位置前移），重复上述操作，直到范围缩小为 1。

代码实现：

// 交换两个整数 void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } // 直接选择排序（升序） void SelectSort(int* a, int n) { int begin = 0, end = n - 1; while (begin < end) { int mini = begin, maxi = begin; // 最小、最大元素下标 // 查找[begin, end]区间内的最小和最大元素 for (int i = begin; i <= end; i++) { if (a[i] < a[mini]) { mini = i; } if (a[i] > a[maxi]) { maxi = i; } } // 处理最小元素（防止最小元素在end位置被覆盖） Swap(&a[mini], &a[begin]); if (begin == maxi) { // 若最大元素在begin位置，交换后maxi应指向mini的原位置 maxi = mini; } // 处理最大元素 Swap(&a[maxi], &a[end]); begin++; end--; } } int main() { int a[] = {5, 3, 9, 6, 2, 4, 7, 1, 8}; int n = sizeof(a) / sizeof(a[0]); printf("直接选择排序前："); PrintArray(a, n); SelectSort(a, n); printf("直接选择排序后："); PrintArray(a, n); return 0; }

特性总结：

• 时间复杂度：O (N²)（最坏 / 平均 / 最好情况，均需遍历查找）
• 空间复杂度：O (1)
• 稳定性：不稳定（例如序列 [5,8,5,2]，第一次交换后两个 5 的相对次序改变）
• 适用场景：数据量小，对稳定性无要求的场景（实际应用中较少使用）

2.2.2 堆排序

原理：堆排序是选择排序的优化版本，利用堆（完全二叉树）的数据结构快速获取最大 / 最小元素。

• 排升序需构建大堆（父节点值≥子节点值），排降序需构建小堆。
• 构建大堆后，堆顶元素为最大值，将其与堆尾元素交换，此时堆尾为有序区。
• 对剩余元素（无序区）重新调整为大堆，重复交换堆顶与堆尾操作，直到无序区为空。

代码实现：

// 堆调整（大堆） void AdjustHeap(int* a, int n, int parent) { int child = 2 * parent + 1; // 左孩子下标 while (child < n) { // 选择较大的孩子 if (child + 1 < n && 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 n) { // 1. 构建大堆（从最后一个非叶子节点开始调整） for (int i = (n - 2) / 2; i >= 0; i--) { AdjustHeap(a, n, i); } // 2. 排序：交换堆顶与堆尾，调整堆 for (int i = n - 1; i > 0; i--) { Swap(&a[0], &a[i]); // 堆顶（最大值）放入有序区 AdjustHeap(a, i, 0); // 调整剩余无序区为大堆 } } int main() { int a[] = {5, 3, 9, 6, 2, 4, 7, 1, 8}; int n = sizeof(a) / sizeof(a[0]); printf("堆排序前："); PrintArray(a, n); HeapSort(a, n); printf("堆排序后："); PrintArray(a, n); return 0; }

特性总结：

• 时间复杂度：O (NlogN)（建堆 O (N)，调整堆 O (NlogN)）
• 空间复杂度：O (1)
• 稳定性：不稳定
• 适用场景：大数据量排序，对空间开销敏感的场景

2.3 交换排序类

交换排序的核心思想是：通过比较两个元素的关键字，若次序错误则交换它们的位置，直到整个序列有序。

2.3.1 冒泡排序

原理：冒泡排序是最基础的交换排序，元素像气泡一样 "上浮" 到对应位置。

• 从序列起始位置开始，依次比较相邻元素，若前元素大于后元素则交换。
• 每一轮遍历后，最大元素会 "冒泡" 到序列末尾（有序区）。
• 优化：若某一轮未发生交换，说明序列已有序，可直接退出。

代码实现：

// 冒泡排序（升序，优化版） void BubbleSort(int* a, int n) { for (int i = 0; i < n; i++) { int exchange = 0; // 标记是否发生交换 // 遍历无序区，相邻元素比较交换 for (int j = 0; j < n - i - 1; j++) { if (a[j] > a[j + 1]) { Swap(&a[j], &a[j + 1]); exchange = 1; } } if (exchange == 0) { break; // 无交换，序列已有序 } } } int main() { int a[] = {5, 3, 9, 6, 2, 4, 7, 1, 8}; int n = sizeof(a) / sizeof(a[0]); printf("冒泡排序前："); PrintArray(a, n); BubbleSort(a, n); printf("冒泡排序后："); PrintArray(a, n); return 0; }

特性总结：

• 时间复杂度：O (N²)（最坏 / 平均情况），O (N)（最好情况，优化后）
• 空间复杂度：O (1)
• 稳定性：稳定
• 适用场景：数据量小或教学场景（实际应用中效率较低）

2.3.2 快速排序

快速排序是 Hoare 于 1962 年提出的高效排序算法，基于分治法思想，是实际应用中最常用的排序算法之一。

原理：

• 选择序列中的一个元素作为基准值（key）。
• 划分：将序列分割为两部分，左部分元素均小于基准值，右部分元素均大于基准值。
• 递归：对左右两部分分别重复上述过程，直到整个序列有序。

核心实现：划分算法快速排序的效率关键在于划分算法，以下实现三种常用划分方式：

（1）Hoare 版本（左右指针法）

// Hoare版本划分 int PartitionHoare(int* a, int left, int right) { int keyi = left; // 基准值下标（选左端点） while (left < right) { // 右指针找比基准值小的元素 while (left < right && a[right] >= a[keyi]) { right--; } // 左指针找比基准值大的元素 while (left < right && a[left] <= a[keyi]) { left++; } // 交换左右指针指向的元素 Swap(&a[left], &a[right]); } // 基准值归位（left=right为基准值的正确位置） Swap(&a[keyi], &a[left]); return left; // 返回基准值下标 } // 快速排序主函数 void QuickSort(int* a, int left, int right) { if (left >= right) { return; // 递归终止条件 } int keyi = PartitionHoare(a, left, right); // 递归排序左区间和右区间 QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); }

（2）挖坑法

// 挖坑法划分 int PartitionHole(int* a, int left, int right) { int key = a[left]; // 基准值（挖坑） int hole = left; // 坑的位置 while (left < right) { // 右指针找比基准值小的元素，填入左坑 while (left < right && a[right] >= key) { right--; } a[hole] = a[right]; hole = right; // 右指针位置变为新坑 // 左指针找比基准值大的元素，填入右坑 while (left < right && a[left] <= key) { left++; } a[hole] = a[left]; hole = left; // 左指针位置变为新坑 } a[hole] = key; // 基准值填入最后一个坑 return hole; } // 快速排序（挖坑法） void QuickSortHole(int* a, int left, int right) { if (left >= right) { return; } int keyi = PartitionHole(a, left, right); QuickSortHole(a, left, keyi - 1); QuickSortHole(a, keyi + 1, right); }

（3）前后指针法（Lomuto 版本）

// 前后指针法划分 int PartitionPrevCur(int* a, int left, int right) { int keyi = left; // 基准值下标 int prev = left; // 前指针（指向小于基准值区域的末尾） int cur = left + 1;// 后指针（遍历序列） while (cur <= right) { // 找到比基准值小的元素，前指针后移并交换 if (a[cur] < a[keyi] && ++prev != cur) { Swap(&a[prev], &a[cur]); } cur++; } // 基准值归位 Swap(&a[keyi], &a[prev]); return prev; } // 快速排序（前后指针法） void QuickSortPrevCur(int* a, int left, int right) { if (left >= right) { return; } int keyi = PartitionPrevCur(a, left, right); QuickSortPrevCur(a, left, keyi - 1); QuickSortPrevCur(a, keyi + 1, right); }

（4）非递归版本（避免栈溢出）

递归版本的快速排序在数据量极大时可能出现栈溢出，非递归版本通过栈模拟递归过程：

#include <stdlib.h> // 栈结构定义（存储区间左右边界） typedef struct Stack { int* data; int top; int capacity; } Stack; // 栈初始化 void StackInit(Stack* st, int capacity) { st->data = (int*)malloc(sizeof(int) * capacity); st->top = -1; st->capacity = capacity; } // 入栈 void StackPush(Stack* st, int val) { st->data[++st->top] = val; } // 出栈 void StackPop(Stack* st) { st->top--; } // 获取栈顶元素 int StackTop(Stack* st) { return st->data[st->top]; } // 栈是否为空 int StackEmpty(Stack* st) { return st->top == -1; } // 栈销毁 void StackDestroy(Stack* st) { free(st->data); st->data = NULL; st->top = -1; st->capacity = 0; } // 快速排序（非递归版本） void QuickSortNonR(int* a, int left, int right) { Stack st; StackInit(&st, right - left + 1); // 初始区间入栈（先入右边界，再入左边界） StackPush(&st, right); StackPush(&st, left); while (!StackEmpty(&st)) { // 出栈获取当前区间 int l = StackTop(&st); StackPop(&st); int r = StackTop(&st); StackPop(&st); // 划分区间 int keyi = PartitionPrevCur(a, l, r); // 右区间入栈（若存在） if (keyi + 1 < r) { StackPush(&st, r); StackPush(&st, keyi + 1); } // 左区间入栈（若存在） if (l < keyi - 1) { StackPush(&st, keyi - 1); StackPush(&st, l); } } StackDestroy(&st); } int main() { int a[] = {5, 3, 9, 6, 2, 4, 7, 1, 8}; int n = sizeof(a) / sizeof(a[0]); printf("快速排序前："); PrintArray(a, n); QuickSort(a, 0, n - 1); // 递归版本 // QuickSortNonR(a, 0, n - 1); // 非递归版本 printf("快速排序后："); PrintArray(a, n); return 0; }

特性总结：

• 时间复杂度：O (NlogN)（平均情况），O (N²)（最坏情况，如有序数组选端点为基准值）
• 空间复杂度：O (logN)（递归栈开销），非递归版本 O (logN)（栈存储区间）
• 稳定性：不稳定
• 适用场景：大数据量排序，是实际应用中效率最高的排序算法之一（需优化基准值选择，如三数取中）

2.4 归并排序

归并排序是基于分治法的稳定排序算法，核心思想是 "先分后合"。

原理：

• 分解：将数组递归拆分为两个子数组，直到每个子数组只有一个元素（天然有序）。
• 合并：将两个有序子数组合并为一个有序数组，重复合并过程直到得到完整的有序数组。

代码实现：

// 合并两个有序子数组 void Merge(int* a, int left, int mid, int right, int* tmp) { int begin1 = left, end1 = mid; // 第一个子数组区间 int begin2 = mid + 1, end2 = right;// 第二个子数组区间 int index = left; // 临时数组下标 // 合并两个有序子数组到临时数组 while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } // 处理剩余元素 while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } // 临时数组元素拷贝回原数组 for (int i = left; i <= right; i++) { a[i] = tmp[i]; } } // 归并排序递归函数 void _MergeSort(int* a, int left, int right, int* tmp) { if (left >= right) { return; // 递归终止条件 } int mid = (left + right) / 2; // 分解左区间和右区间 _MergeSort(a, left, mid, tmp); _MergeSort(a, mid + 1, right, tmp); // 合并两个有序子数组 Merge(a, left, mid, right, tmp); } // 归并排序主函数 void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); // 临时数组（避免递归中重复创建） if (tmp == NULL) { perror("malloc fail"); return; } _MergeSort(a, 0, n - 1, tmp); free(tmp); tmp = NULL; } int main() { int a[] = {5, 3, 9, 6, 2, 4, 7, 1, 8}; int n = sizeof(a) / sizeof(a[0]); printf("归并排序前："); PrintArray(a, n); MergeSort(a, n); printf("归并排序后："); PrintArray(a, n); return 0; }

特性总结：

• 时间复杂度：O (NlogN)（最坏 / 平均 / 最好情况）
• 空间复杂度：O (N)（需要临时数组存储合并结果）
• 稳定性：稳定
• 适用场景：大数据量排序，对稳定性有要求的场景（如多关键字排序）

2.5 非比较排序：计数排序

计数排序不属于比较排序，基于 "鸽巢原理"，通过统计元素出现次数实现排序，适用于数据范围集中的场景。

原理：

• 找出待排序数组中的最大值和最小值，计算数据范围 range = max - min + 1。
• 创建计数数组 count，统计每个元素出现的次数。
• 根据计数数组的统计结果，将元素按顺序放回原数组。

代码实现：

#include <string.h> // 计数排序 void CountSort(int* a, int n) { if (n <= 1) { return; } // 1. 找出最大值和最小值 int min = a[0], max = a[0]; for (int i = 1; i < n; i++) { if (a[i] > max) { max = a[i]; } if (a[i] < min) { min = a[i]; } } // 2. 创建计数数组并初始化 int range = max - min + 1; int* count = (int*)malloc(sizeof(int) * range); if (count == NULL) { perror("malloc fail"); return; } memset(count, 0, sizeof(int) * range); // 3. 统计每个元素出现次数 for (int i = 0; i < n; i++) { count[a[i] - min]++; // 映射到计数数组下标（避免数据范围从0开始） } // 4. 根据计数结果排序 int j = 0; for (int i = 0; i < range; i++) { while (count[i]-- > 0) { a[j++] = i + min; // 恢复原数据 } } free(count); count = NULL; } int main() { int a[] = {6, 1, 2, 9, 4, 2, 4, 1, 4}; int n = sizeof(a) / sizeof(a[0]); printf("计数排序前："); PrintArray(a, n); CountSort(a, n); printf("计数排序后："); PrintArray(a, n); return 0; }

特性总结：

• 时间复杂度：O (N + range)（N 为数据量，range 为数据范围）
• 空间复杂度：O (range)
• 稳定性：稳定（按顺序放回元素可保持相对次序）
• 适用场景：数据范围小且集中的场景（如学生成绩、年龄排序）

三、排序算法性能对比实战

为了直观感受各算法的效率，我们通过测试代码对比 7 种排序算法在 10 万条随机数据下的执行时间（单位：毫秒）。

测试代码

#include <stdio.h> #include <stdlib.h> #include <time.h> #include <string.h> // 此处省略上述所有排序算法的实现（InsertSort、ShellSort、SelectSort、HeapSort、QuickSort、MergeSort、BubbleSort） // 测试排序性能 void TestSortPerformance() { srand(time(0)); const int N = 100000; // 数据量：10万条 // 分配7个数组，存储相同的随机数据 int* a1 = (int*)malloc(sizeof(int) * N); int* a2 = (int*)malloc(sizeof(int) * N); int* a3 = (int*)malloc(sizeof(int) * N); int* a4 = (int*)malloc(sizeof(int) * N); int* a5 = (int*)malloc(sizeof(int) * N); int* a6 = (int*)malloc(sizeof(int) * N); int* a7 = (int*)malloc(sizeof(int) * N); // 生成随机数据 for (int i = 0; i < N; i++) { a1[i] = rand(); a2[i] = a1[i]; a3[i] = a1[i]; a4[i] = a1[i]; a5[i] = a1[i]; a6[i] = a1[i]; a7[i] = a1[i]; } // 测试各排序算法执行时间 clock_t begin, end; // 1. 直接插入排序 begin = clock(); InsertSort(a1, N); end = clock(); printf("直接插入排序：%d ms\n", end - begin); // 2. 希尔排序 begin = clock(); ShellSort(a2, N); end = clock(); printf("希尔排序：%d ms\n", end - begin); // 3. 直接选择排序 begin = clock(); SelectSort(a3, N); end = clock(); printf("直接选择排序：%d ms\n", end - begin); // 4. 堆排序 begin = clock(); HeapSort(a4, N); end = clock(); printf("堆排序：%d ms\n", end - begin); // 5. 快速排序 begin = clock(); QuickSort(a5, 0, N - 1); end = clock(); printf("快速排序：%d ms\n", end - begin); // 6. 归并排序 begin = clock(); MergeSort(a6, N); end = clock(); printf("归并排序：%d ms\n", end - begin); // 7. 冒泡排序 begin = clock(); BubbleSort(a7, N); end = clock(); printf("冒泡排序：%d ms\n", end - begin); // 释放内存 free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7); } int main() { TestSortPerformance(); return 0; }

测试结果（参考）

结果分析

1. 冒泡排序和直接选择排序效率最低，时间复杂度为 O (N²)，不适用于大数据量。
2. 直接插入排序在大数据量下效率较差，但在数据接近有序时表现优异。
3. 希尔排序通过预排序优化，效率远高于直接插入排序，适用于中等数据量。
4. 快速排序、堆排序、归并排序效率最高，时间复杂度为 O (NlogN)，其中快速排序在平均情况下表现最佳。
5. 归并排序是稳定的 O (NlogN) 算法，但需要额外空间；堆排序无需额外空间但不稳定。

四、排序算法选择指南