【C语言-算法-排序】3. 绕不开的"排序"——算法里的重头戏

C语言课上你主要会碰见这么几种：冒泡排序、选择排序、插入排序，还有快速排序。前三个属于"基础款"，代码短、思路直，练的是你循环嵌套的熟练度。快排属于"进阶款"，带递归，考的是你能不能把复杂问题拆简单。

今天咱们挨个拆一遍，不整虚的，直接上代码，一句一句把执行过程说清楚。

例1：冒泡排序——入门第一关，两两比较大的往后冒

冒泡排序是最基础的排序，没有之一。思路特别直观：从头开始，相邻两个数比较，如果前面的比后面的大，就交换。一轮下来，最大的数就"冒"到了最后面。然后对剩下的n-1个数再来一轮，再把其中最大的冒到最后。重复这个操作，直到全部排好。

什么叫"冒泡"？你就想水里的气泡，小的往下沉，大的往上浮。每次相邻比较，大的就往右（后）走，就像气泡往上冒一样。

代码：

#include <stdio.h>

int main() {
    int a[8] = {5, 2, 8, 1, 9, 3, 7, 4};
    int n = 8;
    int i, j, temp;

    // 冒泡排序
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }

    // 输出排序结果
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

拆开看，外层循环和内层循环分别管啥：

外层循环i：控制"一共要冒几轮"。n个数，最多冒n-1轮。为什么是i < n - 1而不是i < n？因为如果只剩下最后一个数没排，它自然就是最小的，不需要再冒了。如果n=8，i从0到6，一共7轮。
内层循环j：控制"这一轮冒到哪儿为止"。每冒完一轮，最后i个数就已经排好了，所以每轮比较的次数就少i次。j < n - 1 - i就是这个意思。
if (a[j] > a[j + 1])：相邻比较，如果前面比后面大，交换。注意是>不是>=，相等的情况不用换，省点事。

追踪第一轮执行过程，看数组怎么变的：

初始：{5, 2, 8, 1, 9, 3, 7, 4}

j=0：比较5和2，5>2，交换，变成{2, 5, 8, 1, 9, 3, 7, 4}
j=1：比较5和8，5不大于8，不变，{2, 5, 8, 1, 9, 3, 7, 4}
j=2：比较8和1，8>1，交换，{2, 5, 1, 8, 9, 3, 7, 4}
j=3：比较8和9，不变，{2, 5, 1, 8, 9, 3, 7, 4}
j=4：比较9和3，9>3，交换，{2, 5, 1, 8, 3, 9, 7, 4}
j=5：比较9和7，交换，{2, 5, 1, 8, 3, 7, 9, 4}
j=6：比较9和4，交换，{2, 5, 1, 8, 3, 7, 4, 9}

第一轮结束，9冒到了最后面。接下来第二轮，i=1，内层只比较到j < 6（也就是前7个数），9不动了。

第二轮走完，8会冒到倒数第二的位置。依次类推，7轮之后全部排好。

冒泡排序的优化：提前结束

如果某一轮一次交换都没发生，说明数组已经有序了，后面的轮次纯属浪费。可以加个标志变量，如果本轮没交换就直接退出。

for (i = 0; i < n - 1; i++) {
    int swapped = 0;
    for (j = 0; j < n - 1 - i; j++) {
        if (a[j] > a[j + 1]) {
            temp = a[j];
            a[j] = a[j + 1];
            a[j + 1] = temp;
            swapped = 1;
        }
    }
    if (swapped == 0) {
        break;   // 没交换，提前结束
    }
}

这个优化在数组基本有序的情况下特别管用。比如{1,2,3,4,5,6,7,8}，第一轮一次交换都没有，直接退出，只比了7次就搞定了。

冒泡排序的复杂度：最坏情况（完全逆序）比较次数是n(n-1)/2，时间复杂度O(n²)。最好情况（已经有序）优化后是O(n)。空间复杂度O(1)，就用了几个临时变量。

这个排序你要能闭着眼睛写出来。不是背，而是脑子里有这个画面——"相邻比较，大的往后走，一轮冒出一个最大的"。

例2：选择排序——每轮挑最小的放到前面

选择排序的思路跟冒泡不一样。它是每轮从待排序的区域里找出最小的那个，放到最前面。第一轮从所有数里找最小的放第0位，第二轮从剩下的数里找最小的放第1位，以此类推。

打个比方，你有一副乱序的扑克牌，你每次从剩下的牌里挑最小的那张，放到手里已排好牌的末尾。

代码：

#include <stdio.h>

int main() {
    int a[8] = {5, 2, 8, 1, 9, 3, 7, 4};
    int n = 8;
    int i, j, minIndex, temp;

    // 选择排序
    for (i = 0; i < n - 1; i++) {
        minIndex = i;   // 假设当前位置就是最小的
        for (j = i + 1; j < n; j++) {
            if (a[j] < a[minIndex]) {
                minIndex = j;   // 发现更小的，记录它的下标
            }
        }
        // 把最小的换到当前位置
        if (minIndex != i) {
            temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
    }

    // 输出
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

拆开看：

外层i从0到n-2，表示当前要确定的位置。
minIndex = i; 先假设当前位置i上的数就是剩余部分里最小的。
内层j从i+1开始，一直到末尾，逐个比较，如果有比a[minIndex]更小的，就更新minIndex指向那个更小的位置。
内层走完，minIndex指向的就是剩余部分里真正的最小值所在位置。
如果minIndex != i，说明最小值不在当前位置，交换它们。

追踪一次执行过程：

初始：{5, 2, 8, 1, 9, 3, 7, 4}

i=0：假设minIndex=0（值是5）。内层从j=1开始找更小的，j=1是2比5小，minIndex=1；j=3是1比2小，minIndex=3；后面没更小的了。交换a[0]和a[3]，变成{1, 2, 8, 5, 9, 3, 7, 4}。1跑到最前面了。
i=1：假设minIndex=1（值是2）。内层从j=2开始找，没有比2更小的（因为1已经排好了），minIndex不变。不交换，位置1本来就是2。
i=2：假设minIndex=2（值是8）。内层找更小的，j=3是5，minIndex=3；j=5是3，minIndex=5。交换a[2]和a[5]，变成{1, 2, 3, 5, 9, 8, 7, 4}。3放到位置2了。
i=3：假设minIndex=3（值是5）。内层找更小的，j=7是4，minIndex=7。交换，变成{1, 2, 3, 4, 9, 8, 7, 5}。

以此类推，最后全部排好。

选择排序和冒泡排序的区别：

冒泡排序每轮可能交换很多次（相邻比较，每次逆序就交换），而选择排序每轮最多交换一次（找到最小值和当前位置交换）。
但选择排序每轮的比较次数跟冒泡一样多，都是O(n²)。
选择排序的交换次数少，在数据量大的时候，交换的开销比比较的开销大，所以选择排序在某些场景下实际跑起来比冒泡快一点。

这个排序你也要能手写出来。思路比冒泡更直观——"挑最小的往前放"，代码写起来也顺。

例3：插入排序——像打牌一样整理手牌

插入排序的思路跟整理扑克牌一样。你从第二张牌开始，把它插入到前面已经排好序的牌里合适的位置。后面的牌依次这么操作。

数组版的思路是：从下标1开始，把当前元素拿出来，跟它前面的元素从后往前比较，如果前面的比它大，就把前面那个往后挪一位，直到找到合适的位置放进去。

代码：

#include <stdio.h>

int main() {
    int a[8] = {5, 2, 8, 1, 9, 3, 7, 4};
    int n = 8;
    int i, j, key;

    // 插入排序
    for (i = 1; i < n; i++) {
        key = a[i];   // 当前要插入的元素
        j = i - 1;

        // 从后往前找，把比key大的都往后挪
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        // 找到合适位置，插入
        a[j + 1] = key;
    }

    // 输出
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

拆开看：

外层i从1开始，因为第0个元素默认已经是"排好序"的。每次处理一个"新牌"。
key = a[i]; 把当前元素暂存起来，因为后面挪动的时候会覆盖它。
j = i - 1; 从当前位置的前一个开始往前找。
while (j >= 0 && a[j] > key)：只要j还没走出界，并且前面的元素比key大，就把前面的元素往后挪一位。a[j + 1] = a[j]; 这就是"往后挪"。
j不断减1，继续往前比。
循环退出的时候，j指向的是第一个不大于key的位置（或者j=-1），把key放到j + 1的位置。

追踪执行过程，特别能说明问题：

初始：{5, 2, 8, 1, 9, 3, 7, 4}

i=1：key=2，j=0。a[0]=5 > 2，把5往后挪到位置1，{5, 5, 8, 1, 9, 3, 7, 4}。j变成-1。循环退出，把key放位置0，变成{2, 5, 8, 1, 9, 3, 7, 4}。
i=2：key=8，j=1。a[1]=5 > 8？不大于，while不执行。把key放位置2（原位），不变。前三个数{2,5,8}已经有序了。
i=3：key=1，j=2。a[2]=8>1，把8挪到位置3，{2,5,8,8,9,3,7,4}，j=1；a[1]=5>1，把5挪到位置2，{2,5,5,8,9,3,7,4}，j=0；a[0]=2>1，把2挪到位置1，{2,2,5,8,9,3,7,4}，j=-1。退出，把key=1放位置0，变成{1,2,5,8,9,3,7,4}。

看到了吗？每次插入都涉及"一串元素整体往后挪一位"，挪动的方向是从后往前。这个操作你在一维数组那篇里见过，插入元素用的就是这招。

插入排序在数据量小或者数据基本有序的情况下效率很高。如果数组本身就是有序的，插入排序只需要O(n)次比较，不需要挪动。但如果是逆序的，那就得全部挪一遍，O(n²)。

这个排序你可能在学校里见的比前两个少一些，但它背后的"整理手牌"逻辑，在实际开发中反而挺常用。

例4：快速排序——分治思想的代表

好，前面三个都是"基础款"，现在来个硬核的。快速排序是C语言教材里最常讲的"进阶排序"，也是实际应用最广泛的排序之一。

快排的核心思想是分治：先选一个"基准"（pivot），把比基准小的放左边，比基准大的放右边，这样基准就排到了它最终应该在的位置。然后对左边和右边递归地执行同样的操作。直到区间只有一个元素，天然有序。

代码（递归版）：

#include <stdio.h>

// 分区函数：把数组分成左右两部分，返回基准的最终位置
int partition(int a[], int left, int right) {
    int pivot = a[left];   // 选最左边作为基准
    int i = left + 1;
    int j = right;
    int temp;

    while (i <= j) {
        // 从左往右找第一个大于pivot的
        while (i <= j && a[i] <= pivot) {
            i++;
        }
        // 从右往左找第一个小于pivot的
        while (i <= j && a[j] > pivot) {
            j--;
        }
        // 如果i和j还没交错，交换它们
        if (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }

    // 把基准放到正确位置（此时j指向最后一个小于pivot的元素）
    temp = a[left];
    a[left] = a[j];
    a[j] = temp;

    return j;   // 返回基准的位置
}

// 快速排序递归函数
void quick_sort(int a[], int left, int right) {
    if (left >= right) {
        return;   // 区间只有一个元素或为空，不用排了
    }
    int pivotIndex = partition(a, left, right);
    quick_sort(a, left, pivotIndex - 1);   // 排左边
    quick_sort(a, pivotIndex + 1, right);  // 排右边
}

int main() {
    int a[8] = {5, 2, 8, 1, 9, 3, 7, 4};
    int n = 8;

    quick_sort(a, 0, n - 1);

    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

这个代码看着有点长，但咱们拆开一步一步看，其实没那么复杂。

先看partition函数在干啥：

它做了三件事：

选a[left]作为基准（pivot）。
用两个指针i从左边往右走，j从右边往左走。i找比基准大的，j找比基准小的，找到就交换。
最后把基准放到j指向的位置，这样基准左边全比它小，右边全比它大。

以数组{5, 2, 8, 1, 9, 3, 7, 4}为例，走一遍第一轮partition：

基准pivot=5，left=0，right=7。

i=1（指向2），j=7（指向4）。

从左找：a[1]=2 <=5，i变成2；a[2]=8 >5，停住。i=2指向8。
从右找：a[7]=4 <=5，停住。j=7指向4。
i < j，交换a[2]和a[7]，数组变成{5, 2, 4, 1, 9, 3, 7, 8}。

继续循环：i=3（指向1），j=6（指向7）。

从左找：a[3]=1 <=5，i变成4；a[4]=9 >5，停住。i=4指向9。
从右找：a[6]=7 >5，j变成5；a[5]=3 <=5，停住。j=5指向3。
i < j，交换a[4]和a[5]，数组变成{5, 2, 4, 1, 3, 9, 7, 8}。

继续循环：i=5（指向9），j=4（指向3）。

从左找：i=5，a[5]=9 >5，停住。
从右找：j=4，a[4]=3 <=5，停住。
i < j？5 < 4不成立，退出循环。

最后把基准a[0]=5和a[j]=a[4]=3交换，数组变成{3, 2, 4, 1, 5, 9, 7, 8}。

此时基准5在位置4，左边{3,2,4,1}全比5小，右边{9,7,8}全比5大。递归快排左边和右边。

quick_sort函数做了什么：

quick_sort(a, 0, 7)
  -> partition返回4
  -> quick_sort(a, 0, 3)   // 排左边
      -> partition返回?（对{3,2,4,1}排）
      -> quick_sort(a, 0, ?)
      -> quick_sort(a, ?, 3)
  -> quick_sort(a, 5, 7)   // 排右边
      -> partition返回?（对{9,7,8}排）
      -> ...

递归的终止条件是left >= right，即区间只有一个元素或者为空。

快排的复杂度：

平均情况：O(n log n)。因为每次分区大概把数组分成两半，递归深度是log n，每层处理n个元素。

最坏情况：O(n²)。比如数组已经有序，每次选的基准都是最小或最大，分区极不平衡，递归深度变成了n。怎么解决？可以随机选基准，或者选左中右三个数的中位数作为基准，尽量避免最坏情况。

空间复杂度：O(log n)，递归调用栈的开销。

快排被认为是实际应用中最好的排序之一，你不需要死记硬背整个代码，但一定要理解"选基准→分区→递归"这个分治框架。能写出来最好，写不出来至少也要能看懂、能复述思路。

四种排序的总结对比：

排序	思路	平均复杂度	最坏复杂度	是否稳定	特点
冒泡排序	相邻比较，大的往后冒	O(n²)	O(n²)	稳定	思路最直观，适合入门
选择排序	每轮挑最小的放前面	O(n²)	O(n²)	不稳定	交换次数少
插入排序	像打牌，逐个插入到已排好部分	O(n²)	O(n²)	稳定	数据基本有序时效率高
快速排序	选基准分区，递归排序	O(n log n)	O(n²)	不稳定	实际应用最广

"稳定"是什么意思？如果数组里有相等的元素，排完序之后它们的相对顺序不变，就叫稳定。冒泡和插入是稳定的，选择和快排不稳定。这个知识点考试可能会问，你心里有数就行。

几个必踩的坑：

坑1：冒泡排序内层循环的n-1-i写不对

很多人写成n-1，每轮都从头比到尾，虽然也能排好，但做了很多无用功。优化了不丢人，说明你知道每一轮后面已经排好的部分不用再比了。

坑2：交换数据时忘了用临时变量

a[j] = a[j + 1]; a[j + 1] = a[j]; 这是最常见的错误写法。你已经把a[j]覆盖了，后面再用a[j]赋值已经不对了。交换必须用第三个临时变量，或者用异或技巧（但不建议，可读性差）。

坑3：快排的递归终止条件漏了

递归函数开头不写if (left >= right) return;，函数会无限递归下去，程序崩溃。这个条件不能省。

坑4：选基准的时候选最左边，遇上已经有序的数组直接变成最坏情况

你学的教材里通常选最左边当基准，这是为了教学方便。实际写代码的时候，可以加两行随机选基准，避免被"故意刁难"。

最后说两句：

排序算法是C语言课程的"大boss"。你把这几种排序都自己敲一遍，跑出正确结果，画一画每轮执行的过程，基本上就摸透了数组和循环的配合。

练到什么程度算过关？ 冒泡和选择能随手写出来，脑子里能模拟一轮的执行过程。插入排序能理解"打牌理牌"的逻辑并写出来。快排能理解分区和递归的思路，能照着框架写出来。做到这些，排序这关你就拿下了。

还是那句话，别光看。每段代码自己敲一遍，数组改大一点（10个、20个），每轮排序之后加个打印，看看数组一步步怎么变的。眼睛看会了不算会，手敲出来、脑子想通了，才算真正是你的。