八大排序算法（C语言实现）—— 从原理到实战，一文搞懂排序

1. 排序算法基础概念

排序算法是计算机科学中最基础的算法之一，它的作用是将一组数据按照特定顺序重新排列。在实际开发中，我们经常需要对数据进行排序，比如按照价格从低到高显示商品，或者按照学生成绩进行排名。

排序算法可以分为两大类：比较排序和非比较排序。比较排序是通过比较元素之间的大小关系来决定它们的顺序，而非比较排序则是通过其他方式（如计数、分配等）来确定元素的顺序。

在C语言中实现排序算法时，我们需要特别注意以下几点：

• 数组作为函数参数传递时实际上是传递指针
• 排序算法的稳定性（相同元素的相对位置是否改变）
• 时间复杂度和空间复杂度的权衡

下面是一个简单的交换函数，后续多个排序算法都会用到：

void Swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; }

2. 直接插入排序

2.1 算法原理

直接插入排序就像我们打扑克牌时整理手牌的过程。假设左手拿的牌已经是有序的，每次从右手摸一张新牌，然后插入到左手合适的位置，保持左手牌始终有序。

算法步骤：

1. 从第一个元素开始，认为它已经是有序的
2. 取出下一个元素，在已排序序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或等于新元素的位置
5. 将新元素插入到该位置后

2.2 C语言实现

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 (tmp < a[end]) { // 需要继续比较 a[end + 1] = a[end]; end--; } else { break; // 找到插入位置 } } a[end + 1] = tmp; } }

2.3 性能分析

• 时间复杂度：

  • 最好情况（已有序）：O(n)
  • 最坏情况（逆序）：O(n²)
  • 平均情况：O(n²)

• 空间复杂度：O(1)，是原地排序算法

• 稳定性：稳定排序算法

直接插入排序适合小规模数据或基本有序的数据集。在实际应用中，当n较小时（通常n≤50），插入排序的性能往往比更复杂的排序算法更好。

3. 希尔排序

3.1 算法原理

希尔排序是插入排序的改进版，由Donald Shell于1959年提出。它通过将原始数组分割成若干子序列，先让这些子序列基本有序，再对全体记录进行插入排序。

算法步骤：

1. 选择一个增量序列t₁,t₂,...,tk，其中ti>tj，tk=1
2. 按增量序列个数k，对序列进行k趟排序
3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序

3.2 C语言实现

void ShellSort(int* a, int n) { int gap = n; while (gap > 1) { gap = gap / 3 + 1; // 动态计算gap值 for (int i = 0; i < n - gap; i++) { int end = i; int tmp = a[end + gap]; while (end >= 0) { if (tmp < a[end]) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } }

3.3 性能分析

• 时间复杂度：取决于增量序列的选择，最好可达到O(n^1.3)
• 空间复杂度：O(1)
• 稳定性：不稳定排序算法

希尔排序是第一个突破O(n²)时间复杂度的排序算法，它使得排序算法的时间复杂度首次降低到亚二次方级别。

4. 选择排序

4.1 算法原理

选择排序是最直观的排序算法之一。它的工作原理是每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

算法步骤：

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2. 从剩余未排序元素中继续寻找最小（大）元素
3. 重复第二步，直到所有元素均排序完毕

4.2 C语言实现

void SelectSort(int* a, int n) { int left = 0; int right = n - 1; while (left < right) { int minIndex = left; int maxIndex = left; // 找出当前范围内的最小和最大值 for (int i = left; i <= right; i++) { if (a[i] < a[minIndex]) minIndex = i; if (a[i] > a[maxIndex]) maxIndex = i; } // 将最小值交换到left位置 Swap(&a[left], &a[minIndex]); // 如果最大值原本在left位置，由于已经交换到minIndex位置了 if (maxIndex == left) maxIndex = minIndex; // 将最大值交换到right位置 Swap(&a[right], &a[maxIndex]); left++; right--; } }

4.3 性能分析

• 时间复杂度：无论最好最坏情况都是O(n²)
• 空间复杂度：O(1)
• 稳定性：不稳定排序算法

选择排序的主要优点是简单直观，交换次数少（最多n-1次），适合数据量较小的情况。

5. 堆排序

5.1 算法原理

堆排序是利用堆这种数据结构所设计的一种排序算法。堆是一种近似完全二叉树的结构，并同时满足堆的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。

算法步骤：

1. 将初始待排序序列构建成大顶堆
2. 将堆顶元素与末尾元素交换，此时末尾为最大元素
3. 调整剩余元素使其成为新堆
4. 重复步骤2-3，直到堆的大小为1

5.2 C语言实现

// 向下调整算法 void AdjustDown(int* a, int n, int root) { int parent = root; 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) { // 建堆：从最后一个非叶子节点开始调整 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } // 排序：每次将堆顶元素与末尾元素交换，然后调整堆 int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); end--; } }

5.3 性能分析

• 时间复杂度：建堆O(n)，排序O(nlogn)，总体O(nlogn)
• 空间复杂度：O(1)
• 稳定性：不稳定排序算法

堆排序适合处理大数据量的排序问题，特别是需要部分排序结果的场景。它的最坏时间复杂度也是O(nlogn)，这是它相对于快速排序的一个优势。

6. 冒泡排序

6.1 算法原理

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

算法步骤：

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对
3. 针对所有的元素重复以上的步骤，除了最后一个
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

6.2 C语言实现

void BubbleSort(int* a, int n) { for (int end = n; end > 0; end--) { int exchange = 0; // 标记该趟排序是否发生交换 for (int i = 1; i < end; i++) { if (a[i - 1] > a[i]) { Swap(&a[i - 1], &a[i]); exchange = 1; } } // 如果该趟没有发生交换，说明数组已经有序 if (exchange == 0) break; } }

6.3 性能分析

• 时间复杂度：

  • 最好情况（已有序）：O(n)
  • 最坏情况（逆序）：O(n²)
  • 平均情况：O(n²)

• 空间复杂度：O(1)

• 稳定性：稳定排序算法

冒泡排序在实际应用中效率较低，主要用于教学目的和小规模数据的排序。它的优化版本（如加入exchange标志）可以在最好情况下达到线性时间复杂度。

7. 快速排序

7.1 算法原理

快速排序使用分治法策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。

算法步骤：

1. 从数列中挑出一个元素，称为"基准"(pivot)
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面
3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序

7.2 C语言实现（Hoare版本）

// Hoare分区法 int PartSort1(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++; } if (left < right) { Swap(&a[left], &a[right]); } } Swap(&a[keyi], &a[left]); return left; } void QuickSort(int* a, int begin, int end) { if (begin >= end) return; // 三数取中优化，避免最坏情况 int mid = GetMidIndex(a, begin, end); Swap(&a[begin], &a[mid]); int keyi = PartSort1(a, begin, end); QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); }

7.3 性能分析

• 时间复杂度：

  • 最好情况：O(nlogn)
  • 最坏情况（已排序）：O(n²)
  • 平均情况：O(nlogn)

• 空间复杂度：O(logn)（递归栈空间）

• 稳定性：不稳定排序算法

快速排序在实际应用中表现优异，是大多数编程语言标准库中的默认排序算法实现。通过合理选择基准值（如三数取中法）可以避免最坏情况的发生。

8. 归并排序

8.1 算法原理

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。

算法步骤：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针超出序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

8.2 C语言实现

void _MergeSort(int* a, int left, int right, int* tmp) { if (left >= right) return; int mid = left + (right - left) / 2; _MergeSort(a, left, mid, tmp); _MergeSort(a, mid + 1, right, tmp); // 合并两个有序数组 int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; int i = left; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } while (begin1 <= end1) tmp[i++] = a[begin1++]; while (begin2 <= end2) tmp[i++] = a[begin2++]; // 拷贝回原数组 for (int j = left; j <= right; j++) { a[j] = tmp[j]; } } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { printf("malloc fail\n"); exit(-1); } _MergeSort(a, 0, n - 1, tmp); free(tmp); }

8.3 性能分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)
• 稳定性：稳定排序算法

归并排序的最大特点是它是一种稳定的O(nlogn)排序算法，这在某些特定场景下非常有用。它的主要缺点是空间复杂度较高，需要额外的存储空间。

9. 计数排序

9.1 算法原理

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法步骤：

1. 找出待排序的数组中最大和最小的元素
2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
4. 反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1

9.2 C语言实现

void CountSort(int* a, int n) { int min = a[0], max = a[0]; for (int i = 1; i < n; i++) { if (a[i] < min) min = a[i]; if (a[i] > max) max = a[i]; } int range = max - min + 1; int* count = (int*)calloc(range, sizeof(int)); if (count == NULL) { printf("calloc fail\n"); exit(-1); } // 统计每个元素出现的次数 for (int i = 0; i < n; i++) { count[a[i] - min]++; } // 根据统计结果将序列回填到原数组 int j = 0; for (int i = 0; i < range; i++) { while (count[i]--) { a[j++] = i + min; } } free(count); }

9.3 性能分析

• 时间复杂度：O(n+k)，其中k是整数的范围
• 空间复杂度：O(n+k)
• 稳定性：稳定排序算法

计数排序在数据范围不大时效率极高，但当数据范围很大时会消耗大量内存。它适合处理整数排序，特别是当数据范围已知且不大的情况。

10. 排序算法比较与选择

10.1 性能对比

10.2 适用场景选择

1. 小规模数据（n≤50）：直接插入排序或选择排序
2. 中等规模数据（50<n≤1000）：希尔排序
3. 大规模数据（n>1000）：
   • 一般情况：快速排序（标准库常用实现）
   • 需要稳定性：归并排序
   • 数据范围已知且不大：计数排序
4. 部分排序需求：堆排序（可以高效获取前k个最大/最小元素）
5. 链表排序：归并排序（链表环境下归并排序的空间复杂度可以优化到O(1)）

在实际项目中，我们通常会根据具体场景选择合适的排序算法。C语言标准库中的qsort函数通常使用快速排序实现，而C++的std::sort则采用了快速排序、堆排序和插入排序的混合算法（Introsort）。

11. 实战应用与优化技巧

11.1 三数取中法优化快速排序

快速排序在最坏情况下（如数组已排序）性能会退化到O(n²)，通过合理选择基准值可以避免这种情况：

// 三数取中，避免快速排序的最坏情况 int GetMidIndex(int* a, int left, int right) { int mid = left + (right - left) / 2; if (a[left] < a[mid]) { if (a[mid] < a[right]) return mid; else if (a[left] < a[right]) return right; else return left; } else { if (a[mid] > a[right]) return mid; else if (a[left] > a[right]) return right; else return left; } }

11.2 小区间优化

对于递归实现的排序算法（如快速排序、归并排序），当待排序区间较小时，递归调用的开销可能超过排序本身。这时可以切换到简单排序算法：

void QuickSortOpt(int* a, int begin, int end) { if (begin >= end) return; // 小区间优化：当区间长度小于一定阈值时，使用插入排序 if (end - begin + 1 <= 10) { InsertSort(a + begin, end - begin + 1); return; } int keyi = PartSort1(a, begin, end); QuickSortOpt(a, begin, keyi - 1); QuickSortOpt(a, keyi + 1, end); }

11.3 非递归实现

递归实现的排序算法在数据量很大时可能导致栈溢出，可以改用栈或队列模拟递归过程：

// 快速排序的非递归实现 void QuickSortNonR(int* a, int begin, int end) { Stack st; StackInit(&st); StackPush(&st, begin); StackPush(&st, end); while (!StackEmpty(&st)) { int right = StackTop(&st); StackPop(&st); int left = StackTop(&st); StackPop(&st); int keyi = PartSort1(a, left, right); // 先压右区间，保证左区间先处理 if (keyi + 1 < right) { StackPush(&st, keyi + 1); StackPush(&st, right); } if (left < keyi - 1) { StackPush(&st, left); StackPush(&st, keyi - 1); } } StackDestroy(&st); }

12. 常见问题与解决方案

12.1 排序算法不稳定怎么办？

如果需要稳定排序，可以选择以下算法：

• 直接插入排序
• 冒泡排序
• 归并排序
• 计数排序

或者为不稳定排序算法添加额外信息来保证稳定性，如在快速排序中，对于相等的元素，可以记录它们的原始位置，在比较时作为第二关键字。

12.2 处理浮点数排序

大多数比较排序算法可以直接用于浮点数排序，但需要注意：

1. 浮点数的相等比较应该使用精度判断而非直接==
2. NaN值的处理需要特别注意，它们与任何值（包括自己）的比较结果都是false

// 浮点数比较函数示例 int compareDouble(const void* a, const void* b) { double diff = *(double*)a - *(double*)b; if (fabs(diff) < 1e-9) return 0; return (diff > 0) ? 1 : -1; }

12.3 处理自定义结构体排序

对于结构体排序，通常需要自定义比较函数：

typedef struct { char name[20]; int age; double score; } Student; // 按分数降序排序，分数相同按年龄升序排序 int compareStudent(const void* a, const void* b) { Student* s1 = (Student*)a; Student* s2 = (Student*)b; if (fabs(s1->score - s2->score) > 1e-9) { return (s1->score > s2->score) ? -1 : 1; } else { return s1->age - s2->age; } } // 使用qsort排序 qsort(students, n, sizeof(Student), compareStudent);

13. 性能测试与对比

为了直观展示不同排序算法的性能差异，我们可以设计一个简单的测试程序：

#include <stdio.h> #include <stdlib.h> #include <time.h> #define TEST_SIZE 10000 void TestSort(const char* sortName, void(*sortFunc)(int*, int), int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); memcpy(tmp, a, sizeof(int) * n); clock_t start = clock(); sortFunc(tmp, n); clock_t end = clock(); double timeUsed = (double)(end - start) / CLOCKS_PER_SEC; printf("%s: %f seconds\n", sortName, timeUsed); free(tmp); } int main() { // 生成随机测试数据 int* a = (int*)malloc(sizeof(int) * TEST_SIZE); for (int i = 0; i < TEST_SIZE; i++) { a[i] = rand() % TEST_SIZE; } // 测试各种排序算法 TestSort("InsertSort", InsertSort, a, TEST_SIZE); TestSort("ShellSort", ShellSort, a, TEST_SIZE); TestSort("SelectSort", SelectSort, a, TEST_SIZE); TestSort("HeapSort", HeapSort, a, TEST_SIZE); TestSort("BubbleSort", BubbleSort, a, TEST_SIZE); TestSort("QuickSort", QuickSort, a, TEST_SIZE); TestSort("MergeSort", MergeSort, a, TEST_SIZE); TestSort("CountSort", CountSort, a, TEST_SIZE); free(a); return 0; }

在我的测试环境中（i7-10750H，Release模式），对10000个随机整数排序的结果大致如下：

• CountSort: 0.0003 seconds
• QuickSort: 0.0012 seconds
• MergeSort: 0.0018 seconds
• HeapSort: 0.0021 seconds
• ShellSort: 0.0035 seconds
• InsertSort: 0.045 seconds
• SelectSort: 0.075 seconds
• BubbleSort: 0.15 seconds

这个测试验证了我们的理论分析：计数排序在数据范围不大时效率最高，O(nlogn)级别的排序算法次之，而O(n²)的算法在大数据量时性能明显下降。

14. 实际项目中的排序应用

在实际C语言项目中，我们通常不会自己实现排序算法，而是使用标准库提供的qsort函数：

#include <stdlib.h> // qsort的比较函数原型 int compare(const void* a, const void* b) { return (*(int*)a - *(int*)b); } int main() { int arr[] = {5, 2, 8, 1, 4}; int n = sizeof(arr) / sizeof(arr[0]); qsort(arr, n, sizeof(int), compare); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }

qsort的优点：

1. 经过高度优化，性能优异
2. 支持任意数据类型
3. 标准库提供，无需额外实现

但在某些特殊场景下，我们可能需要自己实现排序算法：

1. 需要稳定排序而qsort不保证稳定性
2. 数据有特殊性质可以利用（如已知范围、部分有序等）
3. 内存受限环境需要优化空间复杂度
4. 需要并行化排序算法

15. 扩展与进阶

15.1 多线程排序

对于超大规模数据排序，可以考虑使用多线程加速。例如归并排序天然适合并行化：

#include <pthread.h> struct SortArgs { int* a; int left; int right; int* tmp; }; void* ThreadMergeSort(void* args) { struct SortArgs* sa = (struct SortArgs*)args; _MergeSort(sa->a, sa->left, sa->right, sa->tmp); return NULL; } void ParallelMergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); pthread_t thread1, thread2; struct SortArgs sa1 = {a, 0, n/2, tmp}; struct SortArgs sa2 = {a, n/2+1, n-1, tmp}; // 创建两个线程分别排序左右半部分 pthread_create(&thread1, NULL, ThreadMergeSort, &sa1); pthread_create(&thread2, NULL, ThreadMergeSort, &sa2); // 等待线程完成 pthread_join(thread1, NULL); pthread_join(thread2, NULL); // 合并两个有序部分 int begin1 = 0, end1 = n/2; int begin2 = n/2+1, end2 = n-1; int i = 0; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } while (begin1 <= end1) tmp[i++] = a[begin1++]; while (begin2 <= end2) tmp[i++] = a[begin2++]; // 拷贝回原数组 for (int j = 0; j < n; j++) { a[j] = tmp[j]; } free(tmp); }

15.2 外部排序

当数据量太大无法全部装入内存时，需要使用外部排序。常见的外部排序算法是基于归并排序的k路归并：

基本步骤：

1. 将大文件分割成若干能装入内存的小块
2. 对每个小块在内存中排序并写回磁盘
3. 使用多路归并将已排序的小块合并成大文件

// 简化的2路外部排序示例 void ExternalSort(const char* inputFile, const char* outputFile, int chunkSize) { FILE* in = fopen(inputFile, "r"); FILE* out = fopen(outputFile, "w"); int* buffer = (int*)malloc(chunkSize * sizeof(int)); // 第一阶段：分割并内部排序 while (!feof(in)) { int count = fread(buffer, sizeof(int), chunkSize, in); qsort(buffer, count, sizeof(int), compare); char tempFile[100]; sprintf(tempFile, "temp%d.dat", rand()); FILE* tmp = fopen(tempFile, "wb"); fwrite(buffer, sizeof(int), count, tmp); fclose(tmp); } // 第二阶段：多路归并（简化版2路归并） // 实际项目中会使用更高效的多路归并和最小堆优化 // ... free(buffer); fclose(in); fclose(out); }

15.3 基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的时间复杂度是O(nk)，其中k是数字位数。

// 获取数字的某一位（从低位到高位） int GetDigit(int num, int digit) { int divisor = 1; for (int i = 0; i < digit; i++) { divisor *= 10; } return (num / divisor) % 10; } // 基数排序 void RadixSort(int* a, int n) { int max = a[0]; for (int i = 1; i < n; i++) { if (a[i] > max) max = a[i]; } // 计算最大数字的位数 int digits = 0; while (max > 0) { digits++; max /= 10; } // 创建10个桶（0-9） int** buckets = (int**)malloc(10 * sizeof(int*)); int counts[10] = {0}; for (int i = 0; i < 10; i++) { buckets[i] = (int*)malloc(n * sizeof(int)); } // 从低位到高位进行排序 for (int d = 0; d < digits; d++) { // 清空计数器 memset(counts, 0, sizeof(counts)); // 统计每个桶中的元素个数 for (int i = 0; i < n; i++) { int digit = GetDigit(a[i], d); buckets[digit][counts[digit]++] = a[i]; } // 将桶中的元素按顺序写回数组 int k = 0; for (int i = 0; i < 10; i++) { for (int j = 0; j < counts[i]; j++) { a[k++] = buckets[i][j]; } } } // 释放桶内存 for (int i = 0; i < 10; i++) { free(buckets[i]); } free(buckets); }

基数排序适合处理整数且位数不大的情况，特别是当数据范围已知且比较集中时，效率可能超过O(nlogn)的排序算法。