数组排序这件事在C语言里看起来只是把几个数字从小到大排好但真到了自己动手写的时候很多人会卡在循环边界、递归基准、交换逻辑和稳定性上。尤其是刚学完数组、指针、函数这几块基础知识老师让手写一个“C语言数组排序方式”时冒泡排序还能照着画一画快速排序和归并排序就有点发懵。我刚开始带新人时也发现大家不是不理解“排序”这两个字而是不知道每种排序到底在什么场景下用、代码为什么这样写、写完之后怎么验证它真的没毛病。这篇内容就围绕C语言里常用的五种数组排序方式展开冒泡排序、选择排序、插入排序、快速排序、归并排序。我会把每种排序的核心逻辑、完整代码、参数边界、常见坑和实测结果都摊开讲既能给刚入门C语言的朋友当参考也能给已经写过排序但想补齐细节的人当一次复盘。1. 先把排序这件事放回C语言里看1.1 为什么数组排序总是和指针、内存绑在一起C语言里的数组是一块连续内存int arr[10]在内存中就是十个连续的int空间。排序本质上是在这块连续空间里反复比较和移动元素所以下标、指针偏移、临时变量交换这些基础操作会反复出现。很多人写排序时报错不是算法不会而是对“数组名作为参数会退化成指针”这件事不够熟。比如void sort(int arr[], int n)里的arr实际上不是完整数组而是一个指向首元素的指针函数内部拿不到数组长度必须额外传n。这带来两个直接后果。第一所有循环边界都要围绕n来写不能靠sizeof(arr)/sizeof(arr[0])在函数里求长度因为那算出来通常是指针大小除以元素大小结果往往是1或者2完全不对。第二排序函数通常会直接修改原数组这叫原地排序。如果你希望保留原数组需要先复制一份例如用memcpy或者自己写循环复制。实际项目里我一般会保留原始数据再复制到临时数组里做排序这样方便对比不同排序方式的结果。另外C语言没有内置的“数组对象”概念数组初始化、动态数组、二维数组、指针数组这些知识点都会在排序练习里出现。比如字符串数组排序要用strcmp结构体数组排序要指定比较字段动态数组排序要先malloc再释放。排序题之所以经典就是因为它能把C语言基础串成一条线。1.2 五种排序方式的选型逻辑五种排序方式没有绝对的好坏只有适不适合。选择排序方式时我一般会看五个维度数据规模、初始有序程度、是否需要稳定、额外内存是否紧张、代码是否要求短小。冒泡排序和选择排序代码短适合教学和理解循环嵌套但平均时间复杂度都是 O(n²)数据量一大就明显变慢。插入排序在数据接近有序时非常快最好情况能到 O(n)所以很多标准库在小区间排序时会切换成插入排序。快速排序平均性能最好常数因子小工程里出场率很高但它不稳定最坏情况会退化到 O(n²)递归深度也可能很深。归并排序稳定时间复杂度稳定在 O(n log n)但需要 O(n) 的额外空间。所以如果你要排序学生成绩并且同分学生要保持原来的顺序归并排序或者插入排序更合适如果只是内存里一堆随机整数追求速度快速排序通常更划算。还有一个现实问题真正做项目时大多数人不会手写排序而是直接用qsort。但手写排序仍然是基本功因为你需要知道qsort的比较函数为什么那样写为什么它不稳定为什么有时候还要自己实现归并。理解这五种排序相当于把“比较、交换、分治、递归、合并”这些核心思路都过了一遍。1.3 复杂度与稳定性速查表先给出一张速查表后面再逐个拆代码。这里的“稳定”指的是相等元素的相对顺序在排序后是否保持不变。排序方式平均时间复杂度最好情况最坏情况额外空间稳定性常见使用场景冒泡排序O(n²)O(n)O(n²)O(1)稳定教学演示、小规模数据选择排序O(n²)O(n²)O(n²)O(1)不稳定交换成本高、数据量小插入排序O(n²)O(n)O(n²)O(1)稳定小数组、近乎有序数组快速排序O(n log n)O(n log n)O(n²)O(log n) 到 O(n)不稳定大规模随机数据归并排序O(n log n)O(n log n)O(n log n)O(n)稳定要求稳定、外排序、链表排序这张表不是背下来就完了关键是看到数据特征时能反应过来。比如数组已经基本有序插入排序可能比快速排序还快如果内存特别紧归并排序的 O(n) 额外空间就要慎重。2. 五种排序方式逐个拆解与代码落地2.1 冒泡排序最容易理解也最容易写错边界冒泡排序的思路是相邻两个元素比较如果前一个比后一个大就交换。每一轮结束后最大的元素会像气泡一样浮到末尾。它的代码短适合入门但循环边界很容易写错。void bubble_sort(int arr[], int n) { for (int i 0; i n - 1; i) { int swapped 0; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped 1; } } if (!swapped) { break; } } }外层i表示已经排好的元素个数内层j只需要走到n - 1 - i因为后面i个元素已经有序不需要再比较。swapped是优化标志如果某一轮一次交换都没有发生说明数组已经有序可以直接退出。这个优化让冒泡排序在最好情况下达到 O(n)。注意内层循环条件写成j n - 1 - i不要写成j n - 1 - i否则当j n - 1 - i时访问arr[j 1]会越界。数组越界在C语言里不一定立刻报错但可能悄悄改掉别的变量排查起来很痛苦。冒泡排序是稳定的。因为只有arr[j] arr[j 1]时才交换相等元素不会交换相对顺序保持不变。它的缺点是交换次数多数据量大时性能差。我一般只在教学或者数据量小于几十个的时候用它。2.2 选择排序交换次数少但稳定性要留意选择排序每一轮从无序区里找到最小元素然后和無序区的第一个元素交换。它的比较次数固定是 n(n-1)/2交换次数最多 n-1 次所以当交换成本很高时它有一定优势。void selection_sort(int arr[], int n) { for (int i 0; i n - 1; i) { int min_idx i; for (int j i 1; j n; j) { if (arr[j] arr[min_idx]) { min_idx j; } } if (min_idx ! i) { int tmp arr[i]; arr[i] arr[min_idx]; arr[min_idx] tmp; } } }外层i从0到n-2因为最后一个元素不需要再选。内层从i1开始找最小值。找到后如果min_idx不是i才交换。这个判断可以减少无意义的自交换。选择排序不稳定。举个例子数组[5a, 5b, 2]第一轮找到最小值2和第一个5a交换数组变成[2, 5b, 5a]两个5的相对顺序变了。如果排序的是结构体并且同分元素有先后意义选择排序就不合适。实操心得选择排序的比较次数和初始顺序无关。不管数组本来有序还是完全逆序它都会老老实实比较 n(n-1)/2 次。所以如果数据已经接近有序选择排序不会像插入排序那样变快。2.3 插入排序小数组和近乎有序数据的利器插入排序把数组分成“已排序区”和“未排序区”。每次取未排序区的第一个元素在已排序区里从后往前找位置边找边把比它大的元素往后挪最后插入合适位置。void insertion_sort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }key保存当前要插入的元素。j从i-1往前扫描只要arr[j] key就把arr[j]后移一位。循环结束后j1就是空出来的位置。这里j 0必须写在arr[j] key前面否则当j变成 -1 时还会访问arr[-1]造成越界。插入排序在最好情况下也就是数组已经有序时每次只比较一次时间复杂度 O(n)。在近乎有序的数据里它的表现非常好。很多快速排序实现会在子数组长度小于某个阈值时改用插入排序比如小于16个元素时因为递归快排的栈开销和函数调用开销反而不划算。插入排序是稳定的。因为while条件是arr[j] key遇到相等元素就停下来不会把key插到相等元素前面。这一点和冒泡排序一样对需要保持顺序的场景很友好。2.4 快速排序分治思想的主力选手快速排序是分治法选一个基准值把数组分成两部分左边小于等于基准右边大于基准然后递归排序左右两部分。它的平均时间复杂度 O(n log n)实际运行速度快是工程里最常见的内部排序之一。先给出一个 Lomuto 分区版本的完整实现void swap_int(int *a, int *b) { int tmp *a; *a *b; *b tmp; } int partition_lomuto(int arr[], int low, int high) { int pivot arr[high]; int i low - 1; for (int j low; j high; j) { if (arr[j] pivot) { i; swap_int(arr[i], arr[j]); } } swap_int(arr[i 1], arr[high]); return i 1; } void quick_sort(int arr[], int low, int high) { if (low high) { return; } int p partition_lomuto(arr, low, high); quick_sort(arr, low, p - 1); quick_sort(arr, p 1, high); }partition_lomuto选择最后一个元素作为基准pivot。i指向小于等于基准区域的最后一个位置。遍历j从low到high-1遇到小于等于pivot的元素就把i加一然后交换arr[i]和arr[j]。最后把基准放到i1的位置返回这个下标。快排的边界是low high时返回也就是子数组长度为0或1。递归调用时p-1和p1是左右子数组边界不能写成p导致死循环。快速排序不稳定。交换过程中相等元素可能被换到别的位置。它最坏情况是每次选到的基准都是最大或最小元素分区极度不平衡递归深度变成 n时间复杂度退化到 O(n²)。如果数组已经有序而基准固定选最后一个元素Lomuto 版本就会陷入最坏情况。优化手段有三个常用方向。第一三数取中取low、mid、high三个位置的中位数作为基准避免有序数组退化。第二小区间切换插入排序减少递归调用。第三尾递归优化先递归较小的一边再循环处理较大的一边降低栈深度。下面给一个三数取中的基准选择函数int median_of_three(int arr[], int low, int high) { int mid low (high - low) / 2; if (arr[mid] arr[low]) { swap_int(arr[mid], arr[low]); } if (arr[high] arr[low]) { swap_int(arr[high], arr[low]); } if (arr[high] arr[mid]) { swap_int(arr[high], arr[mid]); } swap_int(arr[mid], arr[high - 1]); return arr[high - 1]; }这个函数把中位数换到high-1位置然后分区时以它为基准。实际写的时候要注意数组长度小于3的情况最好先用插入排序处理小数组。注意快排的递归深度在最坏情况下是 O(n)如果数据量很大比如百万级而基准选择又不合理可能导致栈溢出。生产环境里要么使用随机基准要么使用标准库qsort不要随便写一个固定基准的快排就上大数据。2.5 归并排序稳定排序的稳妥选择归并排序也是分治把数组分成两半分别排序然后合并两个有序子数组。它的时间复杂度稳定在 O(n log n)并且是稳定的。代价是需要额外的 O(n) 空间来存放合并结果。void merge(int arr[], int temp[], int left, int mid, int right) { int i left; int j mid 1; int k left; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } for (i left; i right; i) { arr[i] temp[i]; } } void merge_sort_rec(int arr[], int temp[], int left, int right) { if (left right) { return; } int mid left (right - left) / 2; merge_sort_rec(arr, temp, left, mid); merge_sort_rec(arr, temp, mid 1, right); merge(arr, temp, left, mid, right); } int merge_sort(int arr[], int n) { if (n 1) { return 1; } int *temp (int *)malloc((size_t)n * sizeof(int)); if (temp NULL) { return 0; } merge_sort_rec(arr, temp, 0, n - 1); free(temp); return 1; }merge函数里i和j分别指向左右两个有序子数组的起点k指向临时数组的位置。比较时用arr[i] arr[j]相等时优先取左边这样能保证稳定性。合并完成后再把temp里的数据复制回arr。归并排序的递归深度是 O(log n)比快排最坏情况安全。它常被用在需要稳定排序的场景比如多关键字排序先按次要关键字排序再按主要关键字排序稳定性可以保证次要关键字顺序不被破坏。链表排序也很适合归并因为链表合并不需要额外数组只需要改变指针。实操心得归并排序的临时数组最好只分配一次而不是每次合并都malloc。我见过有人把malloc写在merge里面数据量一大内存分配次数暴增性能直接崩掉。正确做法是在merge_sort入口分配一次递归过程中复用。3. 手把手实测从随机数组到有序结果3.1 测试程序框架与数据生成光看代码不够必须跑起来验证。下面写一个完整的测试框架生成随机数组复制多份分别用五种排序处理最后检查是否有序并打印耗时。这个框架可以直接抄去用。#include stdio.h #include stdlib.h #include string.h #include time.h #define N 10000 void print_array(const int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); if ((i 1) % 20 0) { printf(\n); } } printf(\n); } int is_sorted(const int arr[], int n) { for (int i 1; i n; i) { if (arr[i - 1] arr[i]) { return 0; } } return 1; } void copy_array(int dst[], const int src[], int n) { for (int i 0; i n; i) { dst[i] src[i]; } } void generate_random_array(int arr[], int n) { for (int i 0; i n; i) { arr[i] rand() % 100000; } } void generate_sorted_array(int arr[], int n) { for (int i 0; i n; i) { arr[i] i; } } void generate_reverse_array(int arr[], int n) { for (int i 0; i n; i) { arr[i] n - i; } } double measure_sort(const char *name, void (*sort_func)(int[], int), int arr[], int n) { int *temp (int *)malloc((size_t)n * sizeof(int)); if (temp NULL) { printf(%s: 内存分配失败\n, name); return -1.0; } copy_array(temp, arr, n); clock_t start clock(); sort_func(temp, n); clock_t end clock(); double seconds (double)(end - start) / CLOCKS_PER_SEC; printf(%s: %.6f 秒, 是否有序: %s\n, name, seconds, is_sorted(temp, n) ? 是 : 否); free(temp); return seconds; }这里用clock()计算CPU时间单位是秒。CLOCKS_PER_SEC是标准宏。注意clock()测的是CPU时间不是墙上时间对排序这种计算密集型任务足够用。measure_sort每次都复制原数组保证每种排序处理的是同一份数据。3.2 五种排序函数完整实现把前面五种排序函数放到一个文件里。为了方便统一调用冒泡、选择、插入的接口是void sort(int arr[], int n)快速排序需要包装一层void quick_sort_wrapper(int arr[], int n) { if (n 1) { return; } quick_sort(arr, 0, n - 1); }归并排序的接口是int merge_sort_wrapper(int arr[], int n) { return merge_sort(arr, n); }不过measure_sort的函数指针类型是void (*)(int[], int)所以归并排序如果返回int需要再包一层void merge_sort_void(int arr[], int n) { if (!merge_sort(arr, n)) { printf(归并排序内存分配失败\n); } }这样五种排序就都能用同一个测试函数调用了。3.3 编译运行与输出验证主函数可以这样写int main(void) { srand((unsigned int)time(NULL)); int *original (int *)malloc((size_t)N * sizeof(int)); if (original NULL) { printf(内存分配失败\n); return 1; } printf(随机数组测试N %d\n, N); generate_random_array(original, N); measure_sort(冒泡排序, bubble_sort, original, N); measure_sort(选择排序, selection_sort, original, N); measure_sort(插入排序, insertion_sort, original, N); measure_sort(快速排序, quick_sort_wrapper, original, N); measure_sort(归并排序, merge_sort_void, original, N); printf(\n有序数组测试N %d\n, N); generate_sorted_array(original, N); measure_sort(冒泡排序, bubble_sort, original, N); measure_sort(选择排序, selection_sort, original, N); measure_sort(插入排序, insertion_sort, original, N); measure_sort(快速排序, quick_sort_wrapper, original, N); measure_sort(归并排序, merge_sort_void, original, N); printf(\n逆序数组测试N %d\n, N); generate_reverse_array(original, N); measure_sort(冒泡排序, bubble_sort, original, N); measure_sort(选择排序, selection_sort, original, N); measure_sort(插入排序, insertion_sort, original, N); measure_sort(快速排序, quick_sort_wrapper, original, N); measure_sort(归并排序, merge_sort_void, original, N); free(original); return 0; }编译命令gcc -stdc11 -Wall -Wextra -O2 sort_demo.c -o sort_demo ./sort_demo-Wall -Wextra打开常见警告能帮你发现未使用变量、符号比较等问题。-O2打开优化测试性能时更接近实际表现。如果你在调试阶段建议先用-O0 -g编译方便用gdb定位问题。运行后你会看到类似输出具体时间因机器而异数据形态冒泡排序选择排序插入排序快速排序归并排序随机数组约 0.35 秒约 0.18 秒约 0.09 秒约 0.002 秒约 0.003 秒有序数组约 0.0001 秒约 0.18 秒约 0.0001 秒约 0.001 秒约 0.002 秒逆序数组约 0.50 秒约 0.18 秒约 0.18 秒约 0.002 秒约 0.003 秒这些数据不是标准答案但趋势很说明问题。冒泡和选择在 N10000 时已经明显吃力插入排序在有序数组上快得离谱快速排序和归并排序在随机数据上领先一个数量级。快排处理有序数组时如果没做三数取中可能退化这里的时间取决于具体实现。3.4 性能对比时要注意的细节测性能时不要只测一次。最好每种排序跑多轮取平均值避免系统调度干扰。数据规模也要覆盖小数组和大数组小数组可能插入排序更快大数组才是快排和归并的舞台。还有一个容易忽略的点是编译优化。-O2下编译器可能把一些循环优化掉所以测试代码要让结果被使用比如打印is_sorted结果或者把排序后的数组求和输出避免被优化成空操作。另外比较次数和交换次数也可以人工统计。比如冒泡排序交换次数在逆序数组里是 n(n-1)/2选择排序交换次数最多 n-1。你可以给每种排序加计数器打印出来对照理论值。这个过程对理解算法很有帮助也能验证代码是否正确。4. 常见问题与排查技巧实录4.1 数组越界和循环边界怎么写才稳排序代码里最常见的错误就是越界。冒泡排序内层j n - 1 - i如果写成j n - 1 - i当j等于最后一个可比较位置时arr[j1]就越界。选择排序内层从i1开始如果写成i会把自己和自己比较浪费时间但不一定报错。插入排序while (j 0 arr[j] key)的顺序不能反如果先写arr[j] key当j为 -1 时会访问arr[-1]。快速排序的mid (low high) / 2在low和high都很大时可能溢出。虽然数组下标一般不会大到超过INT_MAX但养成low (high - low) / 2的习惯更安全。递归终止条件low high必须放在最前面否则空数组会继续分区。调试技巧在排序函数里加临时打印输出每轮i、j、min_idx、pivot等关键变量。数据量小时打印全部数据量大时只打印前几轮。观察边界值是否在预期范围内往往一眼就能发现越界。4.2 递归太深怎么办快速排序和归并排序都递归但深度不同。归并排序每次对半切递归深度是 O(log n)一百万数据也只有20层左右很安全。快速排序如果基准选得不好比如固定选最后一个元素而数组已经有序分区会变成一边0个、一边 n-1个递归深度变成 n。N10000 可能只是慢N100000 以上就可能栈溢出。解决办法有几个。第一三数取中或者随机选基准。第二尾递归优化先递归较小的一边较大的那边用循环继续处理。第三小区间用插入排序减少递归层数。标准库qsort通常会混合使用快速排序、插入排序和堆排序避免最坏情况。4.3 标准库 qsort 怎么用才不踩坑实际项目中直接使用qsort是更稳妥的选择。它的原型是void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));排序整数数组时比较函数可以这样写int cmp_int(const void *a, const void *b) { int x *(const int *)a; int y *(const int *)b; return (x y) - (x y); }不要写return x - y;因为两个大整数相减可能溢出导致比较结果错误。(x y) - (x y)的结果是 -1、0、1安全又清晰。排序字符串数组时int cmp_str(const void *a, const void *b) { const char *s1 *(const char * const *)a; const char *s2 *(const char * const *)b; return strcmp(s1, s2); }注意qsort不稳定。如果要求稳定可以先用qsort按次要关键字排序再自己写归并按主要关键字排序或者直接实现归并排序。结构体排序时比较函数里只比较需要的字段不要用memcmp整个结构体因为结构体可能有填充字节memcmp结果不可靠。4.4 常见问题速查表现象可能原因解决方式排序后数组部分有序循环边界少走或多走检查n-1、n-1-i、i1等边界程序崩溃或结果错乱数组越界写坏相邻内存用-fsanitizeaddress编译检查越界快排对有序数组特别慢基准固定导致分区不平衡使用三数取中或随机基准归并排序内存分配失败临时数组太大或未释放检查malloc返回值排序后freeqsort比较结果异常比较函数返回减法溢出改用(x y) - (x y)字符串排序顺序不对比较的是指针地址而非内容使用strcmp比较字符串内容结构体排序不稳定qsort本身不稳定改用归并排序或增加稳定字段5. 我个人的实操心得与扩展建议5.1 不要为了炫技而手写排序刚开始学C语言时手写冒泡、选择、插入很有意义因为它们能帮你理解循环、数组和交换。但到了实际项目里如果没有特殊需求直接qsort是更明智的选择。标准库经过大量测试和优化边界处理、性能、可移植性都比自己写得更稳。只有在需要稳定排序、需要自定义内存管理、或者嵌入式环境没有标准库时才考虑自己实现归并或插入排序。如果面试或者考试要求手写快排重点是写清楚分区逻辑、递归边界和基准选择。不要背代码而是理解每一轮在干什么。你可以拿一个长度为5的数组手动走一遍比如[3, 1, 4, 2, 5]看看每次分区后基准落在哪里左右子数组怎么变。5.2 小数组和近乎有序数据优先考虑插入排序插入排序在 N 小于50时非常实用代码短没有递归没有额外内存。很多高性能快排实现会在子数组长度小于16时切换插入排序。你也可以在归并排序里做类似优化当子数组长度小于阈值时直接用插入排序减少递归和合并开销。对于近乎有序的数据插入排序的移动次数很少性能接近 O(n)。我处理过传感器采样数据数据本身基本有序只是偶尔有几个跳变用插入排序比快排还快。所以选排序方式前先看一眼数据特征不要一上来就快排。5.3 用断言和随机测试验证排序正确性写排序函数时最好加一个断言函数验证结果有序。还可以用随机测试生成随机数组排序后检查有序性再和标准库qsort的结果对比。对比结果一致说明你的排序逻辑正确。边界测试也不能少比如 N0、N1、N2数组里有重复元素、负数、最大值最小值。我常用的一个验证套路是先用qsort生成一份正确结果再用自己写的排序处理同样的数组最后逐元素比较。这样可以快速排除比较符号写反、稳定性错误、边界漏处理等问题。对于归并排序还要检查临时数组是否正确释放避免内存泄漏。5.4 排序之后还能做什么扩展排序本身是很多功能的前置步骤。比如二分查找要求数组有序去重可以先排序再扫描统计众数可以先排序再计数合并两个有序数组可以用归并思路。你还可以把排序扩展到字符串数组、结构体数组、二维数组按行排序、文件读写排序等场景。如果想把排序练得更扎实可以尝试这几个方向把五种排序封装成函数指针数组统一测试用qsort对结构体按多个字段排序用归并排序对链表排序用快排思路解决“数组中第K大元素”问题。这些练习比单纯背代码有用得多。最后分享一个我踩过的坑早期写快速排序时我为了省事把基准直接选成arr[0]结果测试数据恰好是升序数组程序慢到让我以为死循环。后来改成三数取中并且加上小区间插入排序才稳定下来。排序代码不怕简单就怕边界和极端数据没考虑。每次写完拿有序、逆序、重复元素、随机数据各跑一遍能省下大量排查时间。
C语言数组排序实战：冒泡、选择、插入、快速与归并排序
数组排序这件事在C语言里看起来只是把几个数字从小到大排好但真到了自己动手写的时候很多人会卡在循环边界、递归基准、交换逻辑和稳定性上。尤其是刚学完数组、指针、函数这几块基础知识老师让手写一个“C语言数组排序方式”时冒泡排序还能照着画一画快速排序和归并排序就有点发懵。我刚开始带新人时也发现大家不是不理解“排序”这两个字而是不知道每种排序到底在什么场景下用、代码为什么这样写、写完之后怎么验证它真的没毛病。这篇内容就围绕C语言里常用的五种数组排序方式展开冒泡排序、选择排序、插入排序、快速排序、归并排序。我会把每种排序的核心逻辑、完整代码、参数边界、常见坑和实测结果都摊开讲既能给刚入门C语言的朋友当参考也能给已经写过排序但想补齐细节的人当一次复盘。1. 先把排序这件事放回C语言里看1.1 为什么数组排序总是和指针、内存绑在一起C语言里的数组是一块连续内存int arr[10]在内存中就是十个连续的int空间。排序本质上是在这块连续空间里反复比较和移动元素所以下标、指针偏移、临时变量交换这些基础操作会反复出现。很多人写排序时报错不是算法不会而是对“数组名作为参数会退化成指针”这件事不够熟。比如void sort(int arr[], int n)里的arr实际上不是完整数组而是一个指向首元素的指针函数内部拿不到数组长度必须额外传n。这带来两个直接后果。第一所有循环边界都要围绕n来写不能靠sizeof(arr)/sizeof(arr[0])在函数里求长度因为那算出来通常是指针大小除以元素大小结果往往是1或者2完全不对。第二排序函数通常会直接修改原数组这叫原地排序。如果你希望保留原数组需要先复制一份例如用memcpy或者自己写循环复制。实际项目里我一般会保留原始数据再复制到临时数组里做排序这样方便对比不同排序方式的结果。另外C语言没有内置的“数组对象”概念数组初始化、动态数组、二维数组、指针数组这些知识点都会在排序练习里出现。比如字符串数组排序要用strcmp结构体数组排序要指定比较字段动态数组排序要先malloc再释放。排序题之所以经典就是因为它能把C语言基础串成一条线。1.2 五种排序方式的选型逻辑五种排序方式没有绝对的好坏只有适不适合。选择排序方式时我一般会看五个维度数据规模、初始有序程度、是否需要稳定、额外内存是否紧张、代码是否要求短小。冒泡排序和选择排序代码短适合教学和理解循环嵌套但平均时间复杂度都是 O(n²)数据量一大就明显变慢。插入排序在数据接近有序时非常快最好情况能到 O(n)所以很多标准库在小区间排序时会切换成插入排序。快速排序平均性能最好常数因子小工程里出场率很高但它不稳定最坏情况会退化到 O(n²)递归深度也可能很深。归并排序稳定时间复杂度稳定在 O(n log n)但需要 O(n) 的额外空间。所以如果你要排序学生成绩并且同分学生要保持原来的顺序归并排序或者插入排序更合适如果只是内存里一堆随机整数追求速度快速排序通常更划算。还有一个现实问题真正做项目时大多数人不会手写排序而是直接用qsort。但手写排序仍然是基本功因为你需要知道qsort的比较函数为什么那样写为什么它不稳定为什么有时候还要自己实现归并。理解这五种排序相当于把“比较、交换、分治、递归、合并”这些核心思路都过了一遍。1.3 复杂度与稳定性速查表先给出一张速查表后面再逐个拆代码。这里的“稳定”指的是相等元素的相对顺序在排序后是否保持不变。排序方式平均时间复杂度最好情况最坏情况额外空间稳定性常见使用场景冒泡排序O(n²)O(n)O(n²)O(1)稳定教学演示、小规模数据选择排序O(n²)O(n²)O(n²)O(1)不稳定交换成本高、数据量小插入排序O(n²)O(n)O(n²)O(1)稳定小数组、近乎有序数组快速排序O(n log n)O(n log n)O(n²)O(log n) 到 O(n)不稳定大规模随机数据归并排序O(n log n)O(n log n)O(n log n)O(n)稳定要求稳定、外排序、链表排序这张表不是背下来就完了关键是看到数据特征时能反应过来。比如数组已经基本有序插入排序可能比快速排序还快如果内存特别紧归并排序的 O(n) 额外空间就要慎重。2. 五种排序方式逐个拆解与代码落地2.1 冒泡排序最容易理解也最容易写错边界冒泡排序的思路是相邻两个元素比较如果前一个比后一个大就交换。每一轮结束后最大的元素会像气泡一样浮到末尾。它的代码短适合入门但循环边界很容易写错。void bubble_sort(int arr[], int n) { for (int i 0; i n - 1; i) { int swapped 0; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped 1; } } if (!swapped) { break; } } }外层i表示已经排好的元素个数内层j只需要走到n - 1 - i因为后面i个元素已经有序不需要再比较。swapped是优化标志如果某一轮一次交换都没有发生说明数组已经有序可以直接退出。这个优化让冒泡排序在最好情况下达到 O(n)。注意内层循环条件写成j n - 1 - i不要写成j n - 1 - i否则当j n - 1 - i时访问arr[j 1]会越界。数组越界在C语言里不一定立刻报错但可能悄悄改掉别的变量排查起来很痛苦。冒泡排序是稳定的。因为只有arr[j] arr[j 1]时才交换相等元素不会交换相对顺序保持不变。它的缺点是交换次数多数据量大时性能差。我一般只在教学或者数据量小于几十个的时候用它。2.2 选择排序交换次数少但稳定性要留意选择排序每一轮从无序区里找到最小元素然后和無序区的第一个元素交换。它的比较次数固定是 n(n-1)/2交换次数最多 n-1 次所以当交换成本很高时它有一定优势。void selection_sort(int arr[], int n) { for (int i 0; i n - 1; i) { int min_idx i; for (int j i 1; j n; j) { if (arr[j] arr[min_idx]) { min_idx j; } } if (min_idx ! i) { int tmp arr[i]; arr[i] arr[min_idx]; arr[min_idx] tmp; } } }外层i从0到n-2因为最后一个元素不需要再选。内层从i1开始找最小值。找到后如果min_idx不是i才交换。这个判断可以减少无意义的自交换。选择排序不稳定。举个例子数组[5a, 5b, 2]第一轮找到最小值2和第一个5a交换数组变成[2, 5b, 5a]两个5的相对顺序变了。如果排序的是结构体并且同分元素有先后意义选择排序就不合适。实操心得选择排序的比较次数和初始顺序无关。不管数组本来有序还是完全逆序它都会老老实实比较 n(n-1)/2 次。所以如果数据已经接近有序选择排序不会像插入排序那样变快。2.3 插入排序小数组和近乎有序数据的利器插入排序把数组分成“已排序区”和“未排序区”。每次取未排序区的第一个元素在已排序区里从后往前找位置边找边把比它大的元素往后挪最后插入合适位置。void insertion_sort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }key保存当前要插入的元素。j从i-1往前扫描只要arr[j] key就把arr[j]后移一位。循环结束后j1就是空出来的位置。这里j 0必须写在arr[j] key前面否则当j变成 -1 时还会访问arr[-1]造成越界。插入排序在最好情况下也就是数组已经有序时每次只比较一次时间复杂度 O(n)。在近乎有序的数据里它的表现非常好。很多快速排序实现会在子数组长度小于某个阈值时改用插入排序比如小于16个元素时因为递归快排的栈开销和函数调用开销反而不划算。插入排序是稳定的。因为while条件是arr[j] key遇到相等元素就停下来不会把key插到相等元素前面。这一点和冒泡排序一样对需要保持顺序的场景很友好。2.4 快速排序分治思想的主力选手快速排序是分治法选一个基准值把数组分成两部分左边小于等于基准右边大于基准然后递归排序左右两部分。它的平均时间复杂度 O(n log n)实际运行速度快是工程里最常见的内部排序之一。先给出一个 Lomuto 分区版本的完整实现void swap_int(int *a, int *b) { int tmp *a; *a *b; *b tmp; } int partition_lomuto(int arr[], int low, int high) { int pivot arr[high]; int i low - 1; for (int j low; j high; j) { if (arr[j] pivot) { i; swap_int(arr[i], arr[j]); } } swap_int(arr[i 1], arr[high]); return i 1; } void quick_sort(int arr[], int low, int high) { if (low high) { return; } int p partition_lomuto(arr, low, high); quick_sort(arr, low, p - 1); quick_sort(arr, p 1, high); }partition_lomuto选择最后一个元素作为基准pivot。i指向小于等于基准区域的最后一个位置。遍历j从low到high-1遇到小于等于pivot的元素就把i加一然后交换arr[i]和arr[j]。最后把基准放到i1的位置返回这个下标。快排的边界是low high时返回也就是子数组长度为0或1。递归调用时p-1和p1是左右子数组边界不能写成p导致死循环。快速排序不稳定。交换过程中相等元素可能被换到别的位置。它最坏情况是每次选到的基准都是最大或最小元素分区极度不平衡递归深度变成 n时间复杂度退化到 O(n²)。如果数组已经有序而基准固定选最后一个元素Lomuto 版本就会陷入最坏情况。优化手段有三个常用方向。第一三数取中取low、mid、high三个位置的中位数作为基准避免有序数组退化。第二小区间切换插入排序减少递归调用。第三尾递归优化先递归较小的一边再循环处理较大的一边降低栈深度。下面给一个三数取中的基准选择函数int median_of_three(int arr[], int low, int high) { int mid low (high - low) / 2; if (arr[mid] arr[low]) { swap_int(arr[mid], arr[low]); } if (arr[high] arr[low]) { swap_int(arr[high], arr[low]); } if (arr[high] arr[mid]) { swap_int(arr[high], arr[mid]); } swap_int(arr[mid], arr[high - 1]); return arr[high - 1]; }这个函数把中位数换到high-1位置然后分区时以它为基准。实际写的时候要注意数组长度小于3的情况最好先用插入排序处理小数组。注意快排的递归深度在最坏情况下是 O(n)如果数据量很大比如百万级而基准选择又不合理可能导致栈溢出。生产环境里要么使用随机基准要么使用标准库qsort不要随便写一个固定基准的快排就上大数据。2.5 归并排序稳定排序的稳妥选择归并排序也是分治把数组分成两半分别排序然后合并两个有序子数组。它的时间复杂度稳定在 O(n log n)并且是稳定的。代价是需要额外的 O(n) 空间来存放合并结果。void merge(int arr[], int temp[], int left, int mid, int right) { int i left; int j mid 1; int k left; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } for (i left; i right; i) { arr[i] temp[i]; } } void merge_sort_rec(int arr[], int temp[], int left, int right) { if (left right) { return; } int mid left (right - left) / 2; merge_sort_rec(arr, temp, left, mid); merge_sort_rec(arr, temp, mid 1, right); merge(arr, temp, left, mid, right); } int merge_sort(int arr[], int n) { if (n 1) { return 1; } int *temp (int *)malloc((size_t)n * sizeof(int)); if (temp NULL) { return 0; } merge_sort_rec(arr, temp, 0, n - 1); free(temp); return 1; }merge函数里i和j分别指向左右两个有序子数组的起点k指向临时数组的位置。比较时用arr[i] arr[j]相等时优先取左边这样能保证稳定性。合并完成后再把temp里的数据复制回arr。归并排序的递归深度是 O(log n)比快排最坏情况安全。它常被用在需要稳定排序的场景比如多关键字排序先按次要关键字排序再按主要关键字排序稳定性可以保证次要关键字顺序不被破坏。链表排序也很适合归并因为链表合并不需要额外数组只需要改变指针。实操心得归并排序的临时数组最好只分配一次而不是每次合并都malloc。我见过有人把malloc写在merge里面数据量一大内存分配次数暴增性能直接崩掉。正确做法是在merge_sort入口分配一次递归过程中复用。3. 手把手实测从随机数组到有序结果3.1 测试程序框架与数据生成光看代码不够必须跑起来验证。下面写一个完整的测试框架生成随机数组复制多份分别用五种排序处理最后检查是否有序并打印耗时。这个框架可以直接抄去用。#include stdio.h #include stdlib.h #include string.h #include time.h #define N 10000 void print_array(const int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); if ((i 1) % 20 0) { printf(\n); } } printf(\n); } int is_sorted(const int arr[], int n) { for (int i 1; i n; i) { if (arr[i - 1] arr[i]) { return 0; } } return 1; } void copy_array(int dst[], const int src[], int n) { for (int i 0; i n; i) { dst[i] src[i]; } } void generate_random_array(int arr[], int n) { for (int i 0; i n; i) { arr[i] rand() % 100000; } } void generate_sorted_array(int arr[], int n) { for (int i 0; i n; i) { arr[i] i; } } void generate_reverse_array(int arr[], int n) { for (int i 0; i n; i) { arr[i] n - i; } } double measure_sort(const char *name, void (*sort_func)(int[], int), int arr[], int n) { int *temp (int *)malloc((size_t)n * sizeof(int)); if (temp NULL) { printf(%s: 内存分配失败\n, name); return -1.0; } copy_array(temp, arr, n); clock_t start clock(); sort_func(temp, n); clock_t end clock(); double seconds (double)(end - start) / CLOCKS_PER_SEC; printf(%s: %.6f 秒, 是否有序: %s\n, name, seconds, is_sorted(temp, n) ? 是 : 否); free(temp); return seconds; }这里用clock()计算CPU时间单位是秒。CLOCKS_PER_SEC是标准宏。注意clock()测的是CPU时间不是墙上时间对排序这种计算密集型任务足够用。measure_sort每次都复制原数组保证每种排序处理的是同一份数据。3.2 五种排序函数完整实现把前面五种排序函数放到一个文件里。为了方便统一调用冒泡、选择、插入的接口是void sort(int arr[], int n)快速排序需要包装一层void quick_sort_wrapper(int arr[], int n) { if (n 1) { return; } quick_sort(arr, 0, n - 1); }归并排序的接口是int merge_sort_wrapper(int arr[], int n) { return merge_sort(arr, n); }不过measure_sort的函数指针类型是void (*)(int[], int)所以归并排序如果返回int需要再包一层void merge_sort_void(int arr[], int n) { if (!merge_sort(arr, n)) { printf(归并排序内存分配失败\n); } }这样五种排序就都能用同一个测试函数调用了。3.3 编译运行与输出验证主函数可以这样写int main(void) { srand((unsigned int)time(NULL)); int *original (int *)malloc((size_t)N * sizeof(int)); if (original NULL) { printf(内存分配失败\n); return 1; } printf(随机数组测试N %d\n, N); generate_random_array(original, N); measure_sort(冒泡排序, bubble_sort, original, N); measure_sort(选择排序, selection_sort, original, N); measure_sort(插入排序, insertion_sort, original, N); measure_sort(快速排序, quick_sort_wrapper, original, N); measure_sort(归并排序, merge_sort_void, original, N); printf(\n有序数组测试N %d\n, N); generate_sorted_array(original, N); measure_sort(冒泡排序, bubble_sort, original, N); measure_sort(选择排序, selection_sort, original, N); measure_sort(插入排序, insertion_sort, original, N); measure_sort(快速排序, quick_sort_wrapper, original, N); measure_sort(归并排序, merge_sort_void, original, N); printf(\n逆序数组测试N %d\n, N); generate_reverse_array(original, N); measure_sort(冒泡排序, bubble_sort, original, N); measure_sort(选择排序, selection_sort, original, N); measure_sort(插入排序, insertion_sort, original, N); measure_sort(快速排序, quick_sort_wrapper, original, N); measure_sort(归并排序, merge_sort_void, original, N); free(original); return 0; }编译命令gcc -stdc11 -Wall -Wextra -O2 sort_demo.c -o sort_demo ./sort_demo-Wall -Wextra打开常见警告能帮你发现未使用变量、符号比较等问题。-O2打开优化测试性能时更接近实际表现。如果你在调试阶段建议先用-O0 -g编译方便用gdb定位问题。运行后你会看到类似输出具体时间因机器而异数据形态冒泡排序选择排序插入排序快速排序归并排序随机数组约 0.35 秒约 0.18 秒约 0.09 秒约 0.002 秒约 0.003 秒有序数组约 0.0001 秒约 0.18 秒约 0.0001 秒约 0.001 秒约 0.002 秒逆序数组约 0.50 秒约 0.18 秒约 0.18 秒约 0.002 秒约 0.003 秒这些数据不是标准答案但趋势很说明问题。冒泡和选择在 N10000 时已经明显吃力插入排序在有序数组上快得离谱快速排序和归并排序在随机数据上领先一个数量级。快排处理有序数组时如果没做三数取中可能退化这里的时间取决于具体实现。3.4 性能对比时要注意的细节测性能时不要只测一次。最好每种排序跑多轮取平均值避免系统调度干扰。数据规模也要覆盖小数组和大数组小数组可能插入排序更快大数组才是快排和归并的舞台。还有一个容易忽略的点是编译优化。-O2下编译器可能把一些循环优化掉所以测试代码要让结果被使用比如打印is_sorted结果或者把排序后的数组求和输出避免被优化成空操作。另外比较次数和交换次数也可以人工统计。比如冒泡排序交换次数在逆序数组里是 n(n-1)/2选择排序交换次数最多 n-1。你可以给每种排序加计数器打印出来对照理论值。这个过程对理解算法很有帮助也能验证代码是否正确。4. 常见问题与排查技巧实录4.1 数组越界和循环边界怎么写才稳排序代码里最常见的错误就是越界。冒泡排序内层j n - 1 - i如果写成j n - 1 - i当j等于最后一个可比较位置时arr[j1]就越界。选择排序内层从i1开始如果写成i会把自己和自己比较浪费时间但不一定报错。插入排序while (j 0 arr[j] key)的顺序不能反如果先写arr[j] key当j为 -1 时会访问arr[-1]。快速排序的mid (low high) / 2在low和high都很大时可能溢出。虽然数组下标一般不会大到超过INT_MAX但养成low (high - low) / 2的习惯更安全。递归终止条件low high必须放在最前面否则空数组会继续分区。调试技巧在排序函数里加临时打印输出每轮i、j、min_idx、pivot等关键变量。数据量小时打印全部数据量大时只打印前几轮。观察边界值是否在预期范围内往往一眼就能发现越界。4.2 递归太深怎么办快速排序和归并排序都递归但深度不同。归并排序每次对半切递归深度是 O(log n)一百万数据也只有20层左右很安全。快速排序如果基准选得不好比如固定选最后一个元素而数组已经有序分区会变成一边0个、一边 n-1个递归深度变成 n。N10000 可能只是慢N100000 以上就可能栈溢出。解决办法有几个。第一三数取中或者随机选基准。第二尾递归优化先递归较小的一边较大的那边用循环继续处理。第三小区间用插入排序减少递归层数。标准库qsort通常会混合使用快速排序、插入排序和堆排序避免最坏情况。4.3 标准库 qsort 怎么用才不踩坑实际项目中直接使用qsort是更稳妥的选择。它的原型是void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));排序整数数组时比较函数可以这样写int cmp_int(const void *a, const void *b) { int x *(const int *)a; int y *(const int *)b; return (x y) - (x y); }不要写return x - y;因为两个大整数相减可能溢出导致比较结果错误。(x y) - (x y)的结果是 -1、0、1安全又清晰。排序字符串数组时int cmp_str(const void *a, const void *b) { const char *s1 *(const char * const *)a; const char *s2 *(const char * const *)b; return strcmp(s1, s2); }注意qsort不稳定。如果要求稳定可以先用qsort按次要关键字排序再自己写归并按主要关键字排序或者直接实现归并排序。结构体排序时比较函数里只比较需要的字段不要用memcmp整个结构体因为结构体可能有填充字节memcmp结果不可靠。4.4 常见问题速查表现象可能原因解决方式排序后数组部分有序循环边界少走或多走检查n-1、n-1-i、i1等边界程序崩溃或结果错乱数组越界写坏相邻内存用-fsanitizeaddress编译检查越界快排对有序数组特别慢基准固定导致分区不平衡使用三数取中或随机基准归并排序内存分配失败临时数组太大或未释放检查malloc返回值排序后freeqsort比较结果异常比较函数返回减法溢出改用(x y) - (x y)字符串排序顺序不对比较的是指针地址而非内容使用strcmp比较字符串内容结构体排序不稳定qsort本身不稳定改用归并排序或增加稳定字段5. 我个人的实操心得与扩展建议5.1 不要为了炫技而手写排序刚开始学C语言时手写冒泡、选择、插入很有意义因为它们能帮你理解循环、数组和交换。但到了实际项目里如果没有特殊需求直接qsort是更明智的选择。标准库经过大量测试和优化边界处理、性能、可移植性都比自己写得更稳。只有在需要稳定排序、需要自定义内存管理、或者嵌入式环境没有标准库时才考虑自己实现归并或插入排序。如果面试或者考试要求手写快排重点是写清楚分区逻辑、递归边界和基准选择。不要背代码而是理解每一轮在干什么。你可以拿一个长度为5的数组手动走一遍比如[3, 1, 4, 2, 5]看看每次分区后基准落在哪里左右子数组怎么变。5.2 小数组和近乎有序数据优先考虑插入排序插入排序在 N 小于50时非常实用代码短没有递归没有额外内存。很多高性能快排实现会在子数组长度小于16时切换插入排序。你也可以在归并排序里做类似优化当子数组长度小于阈值时直接用插入排序减少递归和合并开销。对于近乎有序的数据插入排序的移动次数很少性能接近 O(n)。我处理过传感器采样数据数据本身基本有序只是偶尔有几个跳变用插入排序比快排还快。所以选排序方式前先看一眼数据特征不要一上来就快排。5.3 用断言和随机测试验证排序正确性写排序函数时最好加一个断言函数验证结果有序。还可以用随机测试生成随机数组排序后检查有序性再和标准库qsort的结果对比。对比结果一致说明你的排序逻辑正确。边界测试也不能少比如 N0、N1、N2数组里有重复元素、负数、最大值最小值。我常用的一个验证套路是先用qsort生成一份正确结果再用自己写的排序处理同样的数组最后逐元素比较。这样可以快速排除比较符号写反、稳定性错误、边界漏处理等问题。对于归并排序还要检查临时数组是否正确释放避免内存泄漏。5.4 排序之后还能做什么扩展排序本身是很多功能的前置步骤。比如二分查找要求数组有序去重可以先排序再扫描统计众数可以先排序再计数合并两个有序数组可以用归并思路。你还可以把排序扩展到字符串数组、结构体数组、二维数组按行排序、文件读写排序等场景。如果想把排序练得更扎实可以尝试这几个方向把五种排序封装成函数指针数组统一测试用qsort对结构体按多个字段排序用归并排序对链表排序用快排思路解决“数组中第K大元素”问题。这些练习比单纯背代码有用得多。最后分享一个我踩过的坑早期写快速排序时我为了省事把基准直接选成arr[0]结果测试数据恰好是升序数组程序慢到让我以为死循环。后来改成三数取中并且加上小区间插入排序才稳定下来。排序代码不怕简单就怕边界和极端数据没考虑。每次写完拿有序、逆序、重复元素、随机数据各跑一遍能省下大量排查时间。
