排序入门:冒泡、插入、选择(O(n²) 三件套)

引言:算法的「Hello World」

前面八章我们把数据怎么「装起来」折腾了一遍——链表、栈、队列、动态数组,本质上都是在研究「数据放哪、怎么放、放进去之后怎么拿出来」。可现实里光装还不够,很多时候你得让它有序:成绩单要按分数从高到低、日志要按时间排、电话簿要按姓名字典序。排序这件事,几乎是所有算法教材的开篇第一章,你完全可以把它当成算法入门的「Hello World」——它是你第一次正儿八经地面对「同一个问题、多种解法、各有代价」这件事。

这一章我们手搓三种最朴素、最古老的排序:冒泡、插入、选择。先剧透一个让人血压上来的事实:这哥仨的时间复杂度都是 O(n²),也就是数据量翻一倍、它们慢四倍——这种增长速度放到一万个元素的数组上就要跑上亿次操作,实战里完全不能用。那为什么还要学?因为它们简单到能让你看清楚「排序」这件事到底在做什么。第 10 章我们会上 O(n log n) 的快排和归并,把大数据的活接过去;但在理解快排「分治」那一套之前,你得先在脑子里有一个「老老实实一个一个挪」的底子,后面所有的优化才有抓手。一句话,这一章是地基,不是用来上线生产的。

三种排序我们都用同一个数组 {5, 2, 8, 1, 9, 3} 跑,而且都给它们插上计数器,真跑出每个算法各做了多少次比较、多少次交换——你会发现「大家都是 O(n²)」这件事背后,常数因子和代价结构差得挺远,这正是本章最有意思的部分。

冒泡排序:相邻比较,大的往后冒

冒泡排序的思路最直白:相邻的两个元素比一下,谁大谁往后挪一格。一轮从头扫到尾,最大的那个就被一路「冒泡」推到了数组末尾;下一轮就只剩前 n-1 个元素要处理,再推一个次大的到倒数第二位;以此类推,n 个元素做 n-1 轮就排完了。ISO §6.5.2.1 保证我们能放心用 a[j]、a[j+1] 这种下标去读写数组元素(阶段1 第 10 章钉过的下标语义),只要别越界就行——所以循环边界要写成 j + 1 < n - i,意思是「这一轮比较到倒数第 i+1 个为止」,把已经就位的尾巴排除在外。

展开代码 (共 43 行)收起代码

#include <stdio.h>

/* 冒泡排序:相邻比较,大的往后冒;带 swapped 标志优化。
 * 返回总比较次数,交换次数写进 *out_swaps。*/
static size_t bubble_sort(int* a, size_t n, size_t* out_swaps) {
    size_t compares = 0;
    size_t swaps = 0;
    for (size_t i = 0; i + 1 < n; i++) {
        int swapped = 0; /* 这一轮有没有发生交换 */
        for (size_t j = 0; j + 1 < n - i; j++) {
            compares++;
            if (a[j] > a[j + 1]) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                swaps++;
                swapped = 1;
            }
        }
        if (!swapped) {
            break; /* 这一轮没交换:已经有序,提前结束 */
        }
    }
    *out_swaps = swaps;
    return compares;
}

int main(void) {
    int a[] = {5, 2, 8, 1, 9, 3};
    size_t n = sizeof(a) / sizeof(a[0]);

    size_t swaps = 0;
    size_t compares = bubble_sort(a, n, &swaps);

    printf("result:");
    for (size_t i = 0; i < n; i++) {
        printf(" %d", a[i]);
    }
    printf("\n");
    printf("compares = %zu\n", compares);
    printf("swaps    = %zu\n", swaps);
    return 0;
}

$ gcc -std=c11 -Wall -Wextra bubble.c -o bubble && ./bubble
result: 1 2 3 5 8 9
compares = 14
swaps    = 7

外层那个 swapped 标志是冒泡排序最值得讲的一笔。朴素版冒泡不管数组是不是已经有序了,都会傻乎乎地跑满 n-1 轮——每一轮都把剩下的元素两两比一遍;可你想啊,如果某一轮从头扫到尾一次都没交换,那说明数组已经全排好了,后面几轮纯属浪费时间。于是我们加一个 swapped 标志:这一轮发生交换就置 1,扫完一轮发现它还是 0,直接 break 跳出外层循环。这个优化把冒泡的最好情况——数组本来就排好——压成了 O(n):扫一轮 5 次比较、0 次交换、当场结束。我们拿一个已经排好的数组 {1,2,3,5,8,9} 跑一遍验证,compares = 5、swaps = 0,一轮就退出了——这就是「最好 O(n)」的实锤。当然最坏和平均还是 O(n²),这个标志救不了乱序的命,但聊胜于无、而且几乎零成本。

注意 bubble_sort 是怎么把两个数「传出来」的:比较次数用 return 直接带回来,交换次数用 size_t* out_swaps 这个指针参数写回调用者(阶段2 第 3 章的「指针带出多返回值」套路)。size_t 是 sizeof 的返回类型、专门装「个数/大小」这种非负数(§6.5.3.4,阶段1 第 2 章见过),打印它得用 %zu 而不是 %d——写错是 UB,虽然 gcc 大概率不警告,但换 size_t 不是 int 的平台就炸。

插入排序:像整理扑克牌

插入排序有一个最贴切的类比:整理手里的扑克牌。你左手捏着一摞已经按大小排好的牌,右手从桌上没整理的那堆里摸一张起来,从右往左在左手那摞里找它的位置——遇到比它大的就把它往右挪一个、腾出空来,直到碰到一张不比它大的,把新牌插进这个空。{5,2,8,1,9,3} 这堆,你拿起第一张 5 当底子(一个元素的数组天然有序),然后依次摸起 2、8、1、9、3,每张都往左找位置插进去,六张全摸完,左手那摞就排好了。

为了和冒泡、选择口径一致、能公平对比「交换次数」,我们这里用相邻交换的写法:从 a[i] 往左走,前一个比我大就交换(相当于「挪一格」),一直到前一个不比我大为止。一次交换就是三次赋值,三个算法的「交换」都按这个口径数。

展开代码 (共 41 行)收起代码

#include <stdio.h>

/* 插入排序:像整理扑克牌,把 a[i] 插到前段已排序部分的合适位置。
 * 这里用「相邻交换」写法(j 一边比较一边交换),和冒泡/选择口径一致:
 * 一次 swap = 三次赋值。返回总比较次数,交换次数写进 *out_swaps。*/
static size_t insertion_sort(int* a, size_t n, size_t* out_swaps) {
    size_t compares = 0;
    size_t swaps = 0;
    for (size_t i = 1; i < n; i++) {
        for (size_t j = i; j > 0; j--) {
            compares++;
            if (a[j - 1] > a[j]) {
                int tmp = a[j - 1];
                a[j - 1] = a[j];
                a[j] = tmp;
                swaps++;
            } else {
                break; /* 前段已有序,不必再比 */
            }
        }
    }
    *out_swaps = swaps;
    return compares;
}

int main(void) {
    int a[] = {5, 2, 8, 1, 9, 3};
    size_t n = sizeof(a) / sizeof(a[0]);

    size_t swaps = 0;
    size_t compares = insertion_sort(a, n, &swaps);

    printf("result:");
    for (size_t i = 0; i < n; i++) {
        printf(" %d", a[i]);
    }
    printf("\n");
    printf("compares = %zu\n", compares);
    printf("swaps    = %zu\n", swaps);
    return 0;
}

$ gcc -std=c11 -Wall -Wextra insertion.c -o ins && ./ins
result: 1 2 3 5 8 9
compares = 10
swaps    = 7

看仔细这两个数字:比较 10 次、交换 7 次。交换次数和冒泡一模一样都是 7,这不是巧合——任何「只交换相邻的逆序对」的排序,交换次数都等于数组里逆序对(inversion)的个数,也就是「i<j 但 a[i]>a[j]」的 pair 数。{5,2,8,1,9,3} 的逆序对是 (5,2)(5,1)(5,3)(2,1)(8,1)(8,3)(9,3),正好 7 对;你不管用冒泡还是插入,都得把这 7 对逆序一对一对地消除掉,所以交换次数必然相同。冒泡和插入真正的差别在比较次数:冒泡每轮傻乎乎地把剩下的全比一遍(14 次),而插入排序的内层循环有一个 break——前一段已经排好了,只要前一个不比当前大,就立刻停手,不用再往左比。所以插入的比较次数(10)比冒泡(14)少,平均下来常数因子更小。

这里得提一个工程上的小细节:真实的工程代码里,插入排序几乎不会写成「相邻交换」。因为「交换」是三次赋值(tmp=a; a=b; b=tmp),而插入的本质动作是「往后挪一格再落位」,「挪」只需要一次赋值(a[j+1]=a[j])。所以教科书的标准写法是先把 key = a[i] 拎出来,然后 while (j>0 && a[j-1]>key) { a[j]=a[j-1]; j--; },最后 a[j]=key;——这样每次「腾位」是一次赋值而不是三次,常数小很多。我们这里为了和冒泡、选择放在同一个口径下公平比交换次数,故意用了相邻交换的写法;但你要记住,真正追求性能时,插入排序的「挪+落位」写法比这里更快、而且是大名鼎鼎的快排在小数组上的兜底算法(第 10 章会展开)。

插入排序最讨喜的地方是对近乎有序的数组特别快:数据基本排好、只有零星几个元素错位时,内层循环每次几乎立刻 break,比较次数接近 O(n)、交换次数也很少。所以它是「短数组 + 近乎有序」场景的王者,这一点我们等会儿在三者对比里再回头看。

选择排序:每轮挑最小的,跟首位交换

选择排序的思路最像一个不动脑子的策略:我每一轮就在剩下的没排部分里,把最小的那个挑出来,放到这一段的开头。第 1 轮在 6 个里找最小,放到下标 0;第 2 轮在后 5 个里找最小,放到下标 1;以此类推。和前两种「比较一次就可能换一次」不同,选择排序是「先找、后换」——一轮里它要做很多次比较,但只做一次交换(把找到的最小值和这一段的首位互换)。

展开代码 (共 42 行)收起代码

#include <stdio.h>

/* 选择排序:每轮从未排序部分挑最小的、和未排序首位交换。
 * 返回总比较次数,交换次数写进 *out_swaps。*/
static size_t selection_sort(int* a, size_t n, size_t* out_swaps) {
    size_t compares = 0;
    size_t swaps = 0;
    for (size_t i = 0; i + 1 < n; i++) {
        size_t min = i; /* 未排序段最小值的下标 */
        for (size_t j = i + 1; j < n; j++) {
            compares++;
            if (a[j] < a[min]) {
                min = j;
            }
        }
        if (min != i) { /* 找到更小的才交换 */
            int tmp = a[i];
            a[i] = a[min];
            a[min] = tmp;
            swaps++;
        }
    }
    *out_swaps = swaps;
    return compares;
}

int main(void) {
    int a[] = {5, 2, 8, 1, 9, 3};
    size_t n = sizeof(a) / sizeof(a[0]);

    size_t swaps = 0;
    size_t compares = selection_sort(a, n, &swaps);

    printf("result:");
    for (size_t i = 0; i < n; i++) {
        printf(" %d", a[i]);
    }
    printf("\n");
    printf("compares = %zu\n", compares);
    printf("swaps    = %zu\n", swaps);
    return 0;
}

$ gcc -std=c11 -Wall -Wextra selection.c -o sel && ./sel
result: 1 2 3 5 8 9
compares = 15
swaps    = 3

选择排序的输出特别有它的性格:比较次数 15,三个里面最多;交换次数 3,三个里面最少。比较最多很好理解——它对数据毫无「信任」,不管数组是不是已经排好、不管前一段已经整理过什么,每一轮都把剩下的元素一个不漏地全比一遍:第 1 轮比 5 次、第 2 轮 4 次、…… 加起来正好 $(n-1)+(n-2)+...+1=\frac{n(n-1)}{2}=15$。这个比较次数是写死的,哪怕你喂给它一个已经排好的数组,它还是会做 15 次比较——选择排序没有「最好情况 O(n)」这一说,任何输入都是老老实实的 O(n²)。

但它的强项是交换次数。冒泡和插入每发现一对逆序就得换一次(7 次),而选择排序每轮不管比较多少次,最后只换一次:把这一段的最小值跟首位换过去。n 个元素最多换 n-1 次,而且如果最小值本来就站在首位(min == i),我们还可以省掉这一次——所以 {5,2,8,1,9,3} 跑下来只换了 3 次(第 2 轮最小值 2 已经在位、第 4 轮最小值 5 已在位、第 5 轮最小值 8 已在位,这三轮都跳过了)。这就给选择排序找到了它唯一的实战价值:当「搬运一个元素」特别贵的时候——比如每个元素是一段很大的结构体、或者存在某个慢速介质上——你宁可多花几次比较、也要少做几次交换,这种场景下选择排序反而是三件套里最划算的。

三者对比:时间都是 O(n²),但「内功」差很多

把三个程序的输出摆在一起看,门道就清楚了:

算法	比较次数	交换次数	最好情况	稳定?
冒泡	14	7	O(n)(带 swapped)	稳定
插入	10	7	O(n)(近乎有序时)	稳定
选择	15	3	O(n²)(恒定)	不稳定

三者最坏和平均时间都是 O(n²)、空间都是 O(1)(全部原地操作,不另外开数组),这是它们都「慢」的根源、也是第 10 章要用快排和归并替换它们的原因。可就在「都慢」这个共性之下,差别其实不小:插入排序的比较次数(10)明显比冒泡(14)少,因为内层 break 让它每一步都能省一点;选择排序虽然比较最勤(15),但交换最少(3),而且比较次数是完全确定的——不管输入长什么样都一样,这点在某些需要可预测性能的场合(实时系统、对最坏情况敏感的应用)反而是个优点,虽然我们不会真的拿 O(n²) 去扛实时。

那个「稳定?」列是这一章另一个重点,值得单独拉出来实测。

稳定性:相等的元素,原来的先后还能不能保住

排序算法有一个很容易被新手忽略的属性——稳定性(stability)。它的定义是:当两个元素的排序键相等时,排完之后它们在原数组里的相对先后顺序能不能保住。光听定义你可能觉得「相等的东西谁先谁后有所谓吗」,但实战里这件事非常重要。想象你有一张员工表,先按「部门」排了一遍,现在你想再按「年龄」排一遍——如果排序算法是稳定的,那同一个年龄的人会按部门排在一起(因为第二次排序没打乱他们「部门」那个先后);如果算法不稳定,第二次排序一搅,部门就乱套了。「多关键字排序」就靠稳定性一层一层叠出来,所以稳定不是装饰、是个能用的特性。

冒泡和插入天然稳定,而选择排序天然不稳定——这一节我们就用一段带卫星数据(satellite data)的代码把这件事真跑给你看。我们排序的对象不再是一个光秃秃的 int,而是一个 struct {int value; char tag;},value 是排序键、tag 是「原始先后」的标记(用 A、B 标出谁本来在前)。

展开代码 (共 78 行)收起代码

#include <stdio.h>

/* 稳定性演示:卫星数据 {value, tag},只按 value 排序。
 * 相等的两个元素,排完之后原来的先后(tag 字典序)还能保住,就是稳定。
 * 冒泡/插入用「严格大于才换位」保证稳定;选择做「跨距交换」会打乱相对顺序。*/

typedef struct {
    int value; /* 排序键 */
    char tag;  /* 卫星数据:标记原始先后(A 在 B 前) */
} Item;

static void bubble_sort(Item* a, size_t n) {
    for (size_t i = 0; i + 1 < n; i++) {
        int swapped = 0;
        for (size_t j = 0; j + 1 < n - i; j++) {
            if (a[j].value > a[j + 1].value) { /* 严格大于:相等不换,保稳定 */
                Item tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

static void selection_sort(Item* a, size_t n) {
    for (size_t i = 0; i + 1 < n; i++) {
        size_t min = i;
        for (size_t j = i + 1; j < n; j++) {
            if (a[j].value < a[min].value) {
                min = j;
            }
        }
        if (min != i) { /* 一次交换跨很远,可能把相等的元素翻过去 */
            Item tmp = a[i];
            a[i] = a[min];
            a[min] = tmp;
        }
    }
}

static void print_items(const Item* a, size_t n) {
    for (size_t i = 0; i < n; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d%c", a[i].value, a[i].tag);
    }
    printf("\n");
}

int main(void) {
    /* 同一个 value=2 有两个元素:2A 在 2B 前面;排完若还是 A 在 B 前=稳定 */
    Item base[] = {{2, 'A'}, {2, 'B'}, {1, 'C'}};
    size_t n = sizeof(base) / sizeof(base[0]);

    Item bubble[3];
    Item select[3];
    for (size_t i = 0; i < n; i++) {
        bubble[i] = base[i];
        select[i] = base[i];
    }

    printf("before  : ");
    print_items(base, n);

    bubble_sort(bubble, n);
    printf("bubble  : ");
    print_items(bubble, n);

    selection_sort(select, n);
    printf("select  : ");
    print_items(select, n);
    return 0;
}

$ gcc -std=c11 -Wall -Wextra stability.c -o stab && ./stab
before  : 2A 2B 1C
bubble  : 1C 2A 2B
select  : 1C 2B 2A

这一段输出把稳定性这件事讲透了。原数组 2A 2B 1C——两个 value=2 的元素,2A 在 2B 前面(用 A/B 标记原始先后)。冒泡排完得 1C 2A 2B,两个相等的 2 还是 A 在 B 前,保住了原来的先后,稳定;选择排完得 1C 2B 2A,两个相等的 2 翻成了 B 在 A 前,原来的先后被破坏了,不稳定。

为什么差这么多?关键在两个算法「换元素」的方式。冒泡只换相邻的两个,而且比较用的是严格大于(a[j].value > a[j+1].value)——相等的两个元素绝不会换位,所以它们的相对先后天然保得住。插入排序同理,也是相邻、也是严格大于,所以也稳定。可选择排序呢,它的交换是跨距的——第 1 轮它找到最小值 1C(在下标 2),直接和首位 2A(下标 0)换位,这一下 2A 就被甩到了下标 2(原本 2B 的后面),两个相等的 2 的先后瞬间翻转。这就是「跨距交换」的原罪:它换的不是相邻的逆序对,而是隔着很远的两个位置,中间路过的元素(包括相等的)的相对顺序都可能被搅乱。

这里有一个新手常踩的小坑:冒泡和插入稳定,前提是你比较时写的是严格 > 而不是 >=。一旦你手滑写成 a[j] >= a[j+1] 也交换,那相等的两个也会被换位,稳定性立刻丢——所以「想稳定就用严格大于」这条规矩要刻进肌肉记忆。选择排序的不稳定是它算法结构本身决定的(跨距交换),没法靠改比较运算符救回来;真要稳定的选择排序,得改成「找到最小值后往后挪一格(而不是交换)」,但那就不是经典选择排序了、而且常数变大。

小结

冒泡、插入、选择是排序入门的三件套,它们都老老实实地在 O(n²) 的框架里一个一个挪元素——这个共同的慢,正是第 10 章快排和归并用分治打到 O(n log n) 的起点。但在「都慢」之下,三者的代价结构很不一样:冒泡靠相邻比较把最大值「冒泡」到末尾,加一个 swapped 标志就能让最好情况降到 O(n)(实测已排好的 {1,2,3,5,8,9} 跑一轮就退出,5 次比较、0 次交换);插入排序像整理扑克牌,内层循环 break 让它的比较次数(实测 10)明显少于冒泡(14),对近乎有序的数组尤其快——这也是它在工程上被快排拿去当小数组兜底的根本原因(代价结构上,真实的插入排序会用「挪一格再落位」的一次赋值写法、而不是我们这里为了对齐口径用的相邻交换三次赋值,这一点要记住);选择排序每轮老老实实扫一遍剩余、比较次数恒定为 $\frac{n(n-1)}{2}$(实测 15,任何输入都一样),但每轮只换一次、交换次数最少(实测 3),所以它在「搬运成本高」(大结构体、慢介质)的场景里反而是三件套里最划算的——这一点是它唯一的实战价值,记住就行。稳定性的差别更是个能用的特性:冒泡和插入天然稳定(比较用严格 >、只换相邻,相等的元素先后保得住),选择排序因为「跨距交换」天然不稳定(实测 {2A,2B,1C} 排完 2A/2B 先后翻转);稳定性是「多关键字排序」的基础,选算法时要看清楚。三种排序空间都是 O(1)、全部原地,下标访问越界是 UB(§6.5.2.1,阶段1 第 10 章钉过),所以我们循环边界都老老实实写 j + 1 < n - i、i + 1 < n 这种,不漏不减。下一章我们把这三件套收进抽屉,正式上 O(n log n) 的快排和归并,看「分治」是怎么把平方级的劳动量砍到 n log n 的——届时你会发现,快排在「小数组」上会回头叫插入排序来帮忙,这一章打的地基不会白打。

参考资源

• ISO/IEC 9899:2011 §6.5.2.1(数组下标 a[i] ≡ *(a+i),越界 UB)、§6.5.2.2(函数调用)、§6.5.3.4(sizeof 与 size_t)、§6.5(表达式,求值顺序)
• K. N. King《C Programming: A Modern Approach》第 9 章·9.6 Quicksort(递归排序的雏形,引出排序思想)、编程项目第 1 题(递归版 selection_sort:挑最大放末尾、再递归排前 n-1 个)
• Robert Sedgewick《Algorithms》第 2 章·Sorting(冒泡/插入/选择的稳定性分析、插入排序对近乎有序数据的表现、插入排序当小数组兜底的工程实践)
• 第 10 章:数组(下标、越界、a[i] ≡ *(a+i))、第 7 章:控制流(for/if/break)、第 8 章:函数、阶段2·第 3 章:用指针改调用者的变量(out_swaps 带出多返回值)
• 阶段2·第 9 章:函数指针(qsort 对照——本章的三件套都是写死的 int 升序,qsort 用函数指针做到「任意类型 + 任意比较函数」)、阶段3·第 10 章:快排与归并(O(n log n) 对照,本章是它的起点)、阶段3·第 12 章:大 O(O(n²) 的正式推导、最好/最坏/平均)