企业官网建设流程全解析

数组和排序，这两件事在C语言里有多基础，不用我多说。数组是C语言里最常用的连续存储容器，而排序算法几乎就是算法学习的“普通话”。很多初学者学完数组、循环、函数之后，第一道真正需要“动脑子”的练习题就是给一个乱序数组排个序。我当时学的时候，就是在翁恺老师的C语言练习里反复写这些排序，写到后来发现，这五个基础算法不只是应付考试，它们对理解递归、指针、复杂度、稳定性这些概念都有直接帮助。

这篇文章围绕数组这一数据结构，把五大基础排序算法——冒泡排序、选择排序、插入排序、快速排序、归并排序——全部用C语言手写一遍。每个算法我都会给出完整代码，讲清楚为什么这么写，边界条件怎么处理，哪些地方容易踩坑，以及实测下来是什么表现。适合刚学完数组和函数、想系统整理排序算法的初学者，也适合面试前快速复习，或者工作中需要自己实现排序逻辑的同学参考。

1. 数组与排序：先厘清几个基础概念

1.1 数组的存储结构与排序对象的形态

C语言的数组在内存中是连续存储的，一维数组的元素按下标0到n-1排列。排序算法的输入本质上就是一个一维数组，我们要做的是在数组内部改变元素顺序，所以函数参数通常写成void sort(int arr[], int n)的形式。这里有个C语言特有的坑：数组名作为参数传递时会“退化”为指针，函数里其实拿不到数组长度，所以必须显式传入n。如果你写的排序函数内部还想着sizeof(arr)/sizeof(arr[0])，那结果一定是错的，因为这个arr已经是指针了。

数组初始化和声明也是个常见入门问题。比如int a[10] = {0};会把所有元素初始化为0，而int a[10];里面的值是不确定的。在排序前务必确认数组里存的是有效数据，否则你排出来的可能是“垃圾”。另外，虽然排序主要针对一维数组，但二维数组、指针数组在某些场景下也会涉及排序逻辑，比如指针数组存字符串后按字符串长度排序。不过核心思路相同，只是比较元素的方式不同。本文先用int一维数组把算法本身讲透。

1.2 复杂的度和稳定性先记住一个表

在讲具体算法之前，我建议先把下面这个速查表记下来，然后每讲完一个算法，你回过来看它，理解会更深。

稳定性这个概念，对于很多初学者来说容易忽略。它指的是：如果数组里有两个值相等的元素，排序后它们的相对顺序是否保持不变。能保持就叫稳定，不能就叫不稳定。比如按成绩排序后，如果还要保留原本的学号顺序，稳定排序就比较有用。后面我会在具体算法里解释为什么有的稳定、有的不稳定。空间复杂度这里，快排的O(log n)是递归调用栈消耗，归并的O(n)是临时数组开销，其余三个原地排序没有额外大块内存。

2. 冒泡排序：最直观的交换排序

2.1 算法思想与代码实现

冒泡排序的思想最接近人的直觉：从第一个元素开始，相邻两个元素两两比较，如果前一个比后一个大，就交换位置。这样一轮走完，最大的元素就像气泡一样冒到了数组最后。第二轮再对前面n-1个元素做同样的事，第二大元素会到倒数第二位置。重复n-1轮，整个数组就排好了。

我平时喜欢在代码里加一个swapped标志，用于检测某一轮是否发生过交换。如果某一轮从头到尾都没有交换，说明数组已经有序，提前结束循环。这个优化在最好情况下可以把时间复杂度降到O(n)。

#include <stdio.h> 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控制的是“已经排好末尾多少个元素”。第一轮结束时末尾1个元素定住，第二轮结束时末尾2个元素定住，所以最多n-1轮。内层循环的上界是n - 1 - i，因为末尾i个元素已经有序，不需要再参与比较。如果不减i，虽然也可能排好，但会做大量重复比较，而且当i=0时j到n-1，arr[j+1]访问到arr[n]，越界，程序可能直接崩溃。

2.2 实测心得与常见误区

我拿随机生成的10000个整数的数组测过，冒泡排序在没有优化的情况下大概要0.15秒到0.2秒，加上swapped优化后，随机数据的耗时差别不大，但对本来有序的数据，几乎瞬间完成。它的优点是代码简单、稳定、好理解，缺点是平均和最坏都是O(n^2)，数据量一大就吃不消。所以冒泡排序实战价值不高，主要用在学习阶段。

最常见的误区有两个。第一个是交换变量时写成arr[j] = arr[j+1]; arr[j+1] = arr[j];，结果两个元素变成相同值。交换必须用临时变量tmp，或者使用异或技巧（但不推荐，可读性差）。第二个误区是忘了数组下标从0开始，把j < n - 1 - i写成j < n - i，导致比较范围扩大，不仅慢，还可能越界。建议初学者写完代码后先用n=1、n=2、n=3的小数组测试，再验证大数据。

3. 选择排序：简洁但不稳定的排序

3.1 算法思想与代码实现

选择排序的思路也很简单：每一轮在未排序区间里找到最小元素的下标，然后把它和未排序区间的第一个元素交换。第一轮找到全局最小值放到arr[0]，第二轮在arr[1]到arr[n-1]里找最小值放到arr[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; } } }

选择排序的比较次数是固定的n(n-1)/2，无论数据是否有序，这个数不变。所以它的时间复杂度没有最好最坏之分，都是O(n^2)。但交换次数最多只有n-1次，这一点比冒泡好很多，在某些交换代价很高的场景（比如元素是大型结构体）反而可能更实用。

3.2 边界情况与优化思路

选择排序不稳定，这点很多人想不明白。我举个例子：数组[5, 8, 5, 2]，第一轮找到最小值2在下标3，和下标0的5交换，变成[2, 8, 5, 5]。原来两个5，第一个5（下标0）跑到了第二个5（下标2）的后面，相对顺序变了，所以不稳定。

写选择排序时，最容易忽略的是当min_idx == i时不需要交换，虽然交换也没什么问题，但属于无意义操作，加一个判断更严谨。另外，有一种优化思路是每一轮同时找出最小值和最大值，最小值放前面，最大值放后面，这样排序轮数可以减少一半，但代码里的边界处理复杂度明显增加，容易写错。我个人不推荐初学者用这种优化，老老实实写标准版就好。

4. 插入排序：像整理扑克牌一样

4.1 算法思想与代码实现

插入排序是我个人最喜欢的一个排序算法，因为它和生活经验完全对应：打扑克牌的时候，你抓一张新牌，会把它插入到手里已经有序的牌堆里的正确位置。插入排序就是从左到右，把每个元素往前插入到前面有序序列的合适位置。它处理数组前i个元素时，前i-1个元素已经有序，第i个元素往里插。

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保存当前待插入的元素，因为后面移动元素时会覆盖arr[i]。第二，移动过程不是交换，而是从后往前把比key大的元素逐个后移一位，最后把key放到空出来的位置。整个过程是稳定的，因为遇到等于key的元素时，while循环条件arr[j] > key为假，不会越过相等元素，相等元素的相对顺序得以保留。

4.2 适用场景与性能细节

插入排序在对近乎有序的数组排序时表现异常好，最好情况下只需要O(n)次比较。比如数组原来是[1, 2, 3, 5, 4, 6]，只有5和4是逆序的，插入排序几乎两轮就搞定。很多标准库的快排实现会在递归到小区间（比如小于16个元素）时改用插入排序，就是因为小规模数据下插入排序的常数小、开销低。

写插入排序最常见的坑是while循环的短路顺序。while (j >= 0 && arr[j] > key)里的j >= 0必须写在前面，因为C语言&&运算符从左往右求值，一旦j < 0，后面的arr[j]就不会执行了。如果写成while (arr[j] > key && j >= 0)，当j变成-1时，程序会先访问arr[-1]，这在C语言里是未定义行为，可能读到垃圾值，也可能直接段错误。我在实际调试中就见过这种写法导致的诡异崩溃，排查了很久。

5. 快速排序：分治思想的代表

5.1 递归实现与分区逻辑

快速排序利用分治思想：从数组里选一个基准值（pivot），把数组分成两部分，左边所有元素不大于基准，右边所有元素不小于基准，然后递归对左右两部分排序。它的核心难度在于partition（分区）这一步怎么写得高效且不越界。我这里用经典的“挖坑填数法”，代码比较直观。

int partition(int arr[], int low, int high) { int pivot = arr[low]; int i = low; int j = high; while (i < j) { while (i < j && arr[j] >= pivot) { j--; } arr[i] = arr[j]; while (i < j && arr[i] <= pivot) { i++; } arr[j] = arr[i]; } arr[i] = pivot; return i; } void quick_sort(int arr[], int low, int high) { if (low < high) { int pos = partition(arr, low, high); quick_sort(arr, low, pos - 1); quick_sort(arr, pos + 1, high); } }

解释一下partition的流程。一开始把arr[low]作为基准值，此时arr[low]相当于一个“坑”。先从右往左找第一个小于基准的元素，填到坑里，于是arr[j]变成新坑；然后从左往右找第一个大于基准的元素，填到右边的坑。循环直到i和j相遇，最后把基准值放进相遇位置。这样一轮下来，基准值左边都小于等于它，右边都大于等于它。

调用示例是quick_sort(arr, 0, n-1)，区间是闭区间。如果你写成quick_sort(arr, 0, n)，那partition处理时访问arr[n]就会越界。这是我反复提醒初学者的一条：快速排序的所有边界都是“包含端点”的，递归子区间分别是[low, pos-1]和[pos+1, high]，不能把pos再包含进去。

5.2 退化风险与优化技巧

快速排序的平均时间复杂度是O(n log n)，但最坏情况是O(n^2)。当数组已经有序，而基准值又总是选第一个元素时，每次partition都只能把区间分割成1和n-1两部分，递归树退化为一条链，性能直接崩掉。为了规避这个问题，工程上常用“三数取中”策略：从arr[low]、arr[mid]、arr[high]三个位置取中间值作为基准，并把它交换到low位置。这样能极大降低有序数据下的退化概率。另一种方法是随机选基准，但随机数生成本身有开销。

递归深度也是快速排序的隐患。最坏情况下递归深度达到n，对超大数组可能耗尽函数调用栈空间。我在一个嵌入式项目中就遇到过快速排序排序几万条记录时程序崩溃，查到最后就是递归太深，把有限的栈空间用光了。如果你的运行环境栈很小，或者数据量不可控，要么改用非递归快排（用栈模拟递归），要么直接换归并排序。但大部分桌面环境下，普通几万个数用快排是没问题的。

6. 归并排序：稳定但需要额外空间

6.1 算法思想与代码实现

归并排序也是分治。它将数组不断二分，直到每个子区间只有一个元素，然后把两个有序子区间合并成一个有序区间。这个过程需要额外的临时数组来存储合并结果。归并排序的优点是稳定且时间永远是O(n log n)，缺点是需要O(n)的辅助空间。

void merge(int arr[], int tmp[], 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]) { tmp[k++] = arr[i++]; } else { tmp[k++] = arr[j++]; } } while (i <= mid) { tmp[k++] = arr[i++]; } while (j <= right) { tmp[k++] = arr[j++]; } for (int p = left; p <= right; p++) { arr[p] = tmp[p]; } } void merge_sort(int arr[], int tmp[], int left, int right) { if (left < right) { int mid = left + (right - left) / 2; merge_sort(arr, tmp, left, mid); merge_sort(arr, tmp, mid + 1, right); merge(arr, tmp, left, mid, right); } }

这里mid的计算用了left + (right - left) / 2而不是(left + right) / 2，虽然对普通int数组，后者也不会溢出，但这是一个好习惯，尤其是当left和right很大时，两者相加可能溢出int范围。合并时的关键判断是arr[i] <= arr[j]，这个“等于号”决定了归并排序的稳定性。如果写成<，当arr[i]等于arr[j]时，会把右边的元素先放入tmp，左边相同值的元素相对顺序就变了，排序就变成不稳定。我专门拿[3, 1, 2, 3]这样的用例测试过，写成<后两个3的顺序确实会颠倒。

6.2 内存分配与边界检查

归并排序需要一个临时数组tmp。常见错误是在递归函数里频繁分配和释放tmp，这样不仅低效，还可能因为多次malloc导致内存碎片。正确做法是在对外接口里一次性分配好临时数组，再调用递归的merge_sort。

#include <stdlib.h> void merge_sort_wrapper(int arr[], int n) { if (n <= 0) { return; } int *tmp = (int *)malloc(n * sizeof(int)); if (tmp == NULL) { return; } merge_sort(arr, tmp, 0, n - 1); free(tmp); }

同时要注意n=0或n=1的情况，前者malloc(0)可能返回非NULL也可能返回NULL，但都不该去访问内存；后者递归里left==right，直接返回。如果你在主程序里直接调用merge_sort(arr, tmp, 0, n)，那也是错的，因为right=n超出了有效下标范围，循环会访问arr[n]。归并排序所有区间都是闭区间，我建议把对外接口单独封装，让调用者只传数组和长度，避免搞混起始位置。

7. 五大排序横向对比与选型建议

7.1 复杂度与稳定性速查表

我把前面零散提到的信息整理成一张表，方便你随时查阅。

这张表里最容易混淆的是“最坏”和“空间”。快速排序最坏O(n^2)可能让人意外，但只要你理解了退化原因，就明白应该避免在有序数组上直接选首个元素做基准。归并排序时间稳定，但因为要拷贝到临时数组再拷回来，实际常数因子比快速排序大，所以数据量相同时，归并排序往往比快排稍慢，除非要求稳定性。

7.2 根据场景选择算法

我的经验是，选排序算法不能只看复杂度，还要看数据规模、是否要求稳定、内存限制、是否几乎有序。数据量小于50时，插入排序往往比快速排序还快，因为它的常数小，不需要递归。数据量在几千到几百万且不要求稳定性时，快速排序是默认选择。数据量大且业务上要求稳定时，归并排序更合适。如果数据近乎有序，插入排序是最好的选择。如果内存极其有限，只能原地排序，那就只能在冒泡、选择、插入、快排里选，再综合考虑稳定性。

另外，C标准库自带qsort，它内部是经过精心调优的快速排序（可能混合插入排序），绝大多数情况下我们不需要自己写快排。但自己手写一遍这五个算法，意义在于理解它的缺陷和优化点，这样用qsort时你能知道为什么它的参数里要传入比较函数，为什么它的复杂度不是绝对有保障。

8. 数组排序实战中的常见问题与排查

8.1 数组越界与下标错位

C语言数组越界是不会自动提示的，这是新手最容易栽的跟头。比如冒泡排序里内层循环如果写j < n - i，当i为0时j最大到n-1，访问arr[j+1]就是arr[n]，越界。再比如快速排序递归调用时把high写成n，partition里就会访问arr[n]。排查这类问题，我建议三个办法：先用n=1和n=2的小数组跑一遍；在排序函数入口打印low、high和n的值，观察是否合理；如果用GCC编译，可以加-fsanitize=address，它能直接报告越界位置，比你自己盯代码高效得多。

还有一种很隐蔽的错误：排序函数的参数是数组和长度，但你在循环里把长度写成了sizeof(arr)/sizeof(arr[0])。就像前面说的，数组参数退化成指针，sizeof(arr)是一个指针的大小（通常是8字节），除以4以后得到2，导致循环只处理前两个元素。这种错误在64位系统上尤其常见，因为指针大小和int大小不一样。

8.2 递归栈溢出与排序性能陷阱

快速排序和归并排序都用递归。快排在极端情况下递归深度等于n，如果n是十万，而环境栈空间只有几百KB，每层递归即使只占用几十字节，也可能栈溢出。归并排序的递归深度固定为log2(n)，一般不会栈溢出，但它需要额外数组分配。我建议在使用递归排序时，给数据规模设一个上限，或者提前对数组做一次“是否明显有序”的检测，避开最坏情况。

排查这类问题，可以在main函数里设置一个较大的数组（比如100000个元素），连续多次调用排序函数，观察是否崩溃。如果崩溃，优先怀疑栈溢出，可以临时把数组规模降到10000试一试。对于归并排序，还要检查malloc的返回值，返回NULL时不要直接往下走，否则解引用空指针必挂。我在Windows和Linux下都遇到过系统资源紧张导致malloc失败的情况，所以封装函数里一定要判断。

8.3 排序函数的工程化封装要点

写实际可用的排序模块时，我通常会把内部实现和对外接口分开。比如冒泡排序直接暴露bubble_sort(arr, n)没问题，但快速排序和归并排序会暴露复杂参数（low/high或tmp），这时封装一层能有效防止调用者传错。另外，数组里的元素类型不总是int，如果你要排序结构体数组，只要把比较逻辑抽出来单独写一个函数，或者写成宏，就能复用排序框架。C语言里最灵活的是函数指针，但作为入门阶段的五个基础算法，先用int把逻辑吃透更重要。

我还想提一个容易被忽略的问题：排序过程中如果数组里存在大量重复元素，快速排序的性能也会退化。因为经典的partition把等于基准的元素分散到两侧，导致区间分割不均匀。解决方法是三路快排，把数组分成小于、等于、大于基准的三部分，等于基准的不用再递归。这个思路可以作为进阶练习，但它已经超出了基础五排序的范围。建议你先把基础算法写熟，再去研究三路快排、堆排序这些扩展内容。

最后再分享一点我的个人经验

这几个算法我前前后后写了不下几十遍，每次写都还能发现一些细节问题。我现在写排序时，会习惯性在测试函数里用一个print_array函数，每次排序后打印前几个和后几个元素，快速确认没有越界或丢失数据。你去看很多开源代码，里面排序函数旁边都会带一个简单的验证数组，就是这个原因。另外，我强烈建议你把每个算法都亲自敲一遍，不要复制粘贴，敲的过程中才能注意到变量名、边界条件和交换逻辑。等你手写熟之后，再回头用qsort处理实际问题，会轻松很多。排序是算法的起点，也是理解C语言内存和指针的一扇门，希望这篇文章能帮你把这扇门推开。