1. 排序算法基础概念排序算法是计算机科学中最基础的算法之一它的作用是将一组数据按照特定顺序重新排列。在实际开发中我们经常需要对数据进行排序比如按照价格从低到高显示商品或者按照学生成绩进行排名。排序算法可以分为两大类比较排序和非比较排序。比较排序是通过比较元素之间的大小关系来决定它们的顺序而非比较排序则是通过其他方式如计数、分配等来确定元素的顺序。在C语言中实现排序算法时我们需要特别注意以下几点数组作为函数参数传递时实际上是传递指针排序算法的稳定性相同元素的相对位置是否改变时间复杂度和空间复杂度的权衡下面是一个简单的交换函数后续多个排序算法都会用到void Swap(int* a, int* b) { int temp *a; *a *b; *b temp; }2. 直接插入排序2.1 算法原理直接插入排序就像我们打扑克牌时整理手牌的过程。假设左手拿的牌已经是有序的每次从右手摸一张新牌然后插入到左手合适的位置保持左手牌始终有序。算法步骤从第一个元素开始认为它已经是有序的取出下一个元素在已排序序列中从后向前扫描如果该元素已排序大于新元素将该元素移到下一位置重复步骤3直到找到已排序的元素小于或等于新元素的位置将新元素插入到该位置后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年提出。它通过将原始数组分割成若干子序列先让这些子序列基本有序再对全体记录进行插入排序。算法步骤选择一个增量序列t₁,t₂,...,tk其中titjtk1按增量序列个数k对序列进行k趟排序每趟排序根据对应的增量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 算法原理选择排序是最直观的排序算法之一。它的工作原理是每次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完。算法步骤在未排序序列中找到最小大元素存放到排序序列的起始位置从剩余未排序元素中继续寻找最小大元素重复第二步直到所有元素均排序完毕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 算法原理堆排序是利用堆这种数据结构所设计的一种排序算法。堆是一种近似完全二叉树的结构并同时满足堆的性质即子节点的键值或索引总是小于或者大于它的父节点。算法步骤将初始待排序序列构建成大顶堆将堆顶元素与末尾元素交换此时末尾为最大元素调整剩余元素使其成为新堆重复步骤2-3直到堆的大小为15.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 算法原理冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列一次比较两个元素如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。算法步骤比较相邻的元素。如果第一个比第二个大就交换它们两个对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对针对所有的元素重复以上的步骤除了最后一个持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较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 算法原理快速排序使用分治法策略来把一个序列分为较小和较大的两个子序列然后递归地排序两个子序列。算法步骤从数列中挑出一个元素称为基准(pivot)重新排序数列所有比基准值小的元素摆放在基准前面所有比基准值大的元素摆在基准后面递归地把小于基准值元素的子数列和大于基准值元素的子数列排序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 算法原理归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。算法步骤申请空间使其大小为两个已经排序序列之和该空间用来存放合并后的序列设定两个指针最初位置分别为两个已经排序序列的起始位置比较两个指针所指向的元素选择相对小的元素放入到合并空间并移动指针到下一位置重复步骤3直到某一指针超出序列尾将另一序列剩下的所有元素直接复制到合并序列尾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 算法原理计数排序不是基于比较的排序算法其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序计数排序要求输入的数据必须是有确定范围的整数。算法步骤找出待排序的数组中最大和最小的元素统计数组中每个值为i的元素出现的次数存入数组C的第i项对所有的计数累加从C中的第一个元素开始每一项和前一项相加反向填充目标数组将每个元素i放在新数组的第C[i]项每放一个元素就将C[i]减去19.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(nk)其中k是整数的范围空间复杂度O(nk)稳定性稳定排序算法计数排序在数据范围不大时效率极高但当数据范围很大时会消耗大量内存。它适合处理整数排序特别是当数据范围已知且不大的情况。10. 排序算法比较与选择10.1 性能对比排序算法平均时间复杂度最好情况最坏情况空间复杂度稳定性直接插入排序O(n²)O(n)O(n²)O(1)稳定希尔排序O(n^1.3)O(n)O(n²)O(1)不稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定冒泡排序O(n²)O(n)O(n²)O(1)稳定快速排序O(nlogn)O(nlogn)O(n²)O(logn)不稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定计数排序O(nk)O(nk)O(nk)O(nk)稳定10.2 适用场景选择小规模数据n≤50直接插入排序或选择排序中等规模数据50n≤1000希尔排序大规模数据n1000一般情况快速排序标准库常用实现需要稳定性归并排序数据范围已知且不大计数排序部分排序需求堆排序可以高效获取前k个最大/最小元素链表排序归并排序链表环境下归并排序的空间复杂度可以优化到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 处理浮点数排序大多数比较排序算法可以直接用于浮点数排序但需要注意浮点数的相等比较应该使用精度判断而非直接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-10750HRelease模式对10000个随机整数排序的结果大致如下CountSort: 0.0003 secondsQuickSort: 0.0012 secondsMergeSort: 0.0018 secondsHeapSort: 0.0021 secondsShellSort: 0.0035 secondsInsertSort: 0.045 secondsSelectSort: 0.075 secondsBubbleSort: 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的优点经过高度优化性能优异支持任意数据类型标准库提供无需额外实现但在某些特殊场景下我们可能需要自己实现排序算法需要稳定排序而qsort不保证稳定性数据有特殊性质可以利用如已知范围、部分有序等内存受限环境需要优化空间复杂度需要并行化排序算法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/21, 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/21, 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路归并基本步骤将大文件分割成若干能装入内存的小块对每个小块在内存中排序并写回磁盘使用多路归并将已排序的小块合并成大文件// 简化的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)的排序算法。