冒泡排序与插入排序
简单排序
冒泡排序与插入排序 是 CoddyKit 上的免费 C Academy 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 C Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 C Academy 课程共包含 4 节课。
简单排序
冒泡排序和插入排序是最简单的两种比较排序。两者在最坏情况下都是 O(n²)，但容易理解，并且适用于较小或接近有序的数组。
冒泡排序的工作原理
冒泡排序会反复遍历数组，交换相邻的逆序元素对。每次完整遍历后，剩余元素中最大的元素会冒泡到末尾的最终位置。
交换两个整数
可复用的交换辅助函数可以让排序代码更加简洁。
#include <stdio.h>
void swap(int *a, int *b) {
int t = *a; *a = *b; *b = t;
}
int main(void) {
int x = 1, y = 2;
swap(&x, &y);
printf("%d %d\n", x, y);
return 0;
}冒泡排序的实现
使用嵌套循环：外层循环统计遍历次数，内层循环比较相邻元素对并进行交换。完成第 i 次遍历后，最后的 i 个元素已经排好序。
#include <stdio.h>
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
bubble_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}提前退出优化
如果一次完整遍历没有发生任何交换，说明数组已经有序，可以停止排序。这样，冒泡排序在输入已经有序时的复杂度为 O(n)。
#include <stdio.h>
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0;
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swapped = 1;
}
if (!swapped) break;
}
}
int main(void) {
int a[] = {1, 2, 3, 4, 5};
bubble_sort(a, 5);
printf("sorted with early exit\n");
return 0;
}插入排序的工作原理
插入排序会在数组前部构建一个有序区域。对于每个新元素，它将较大的有序元素向右移动，然后把新元素放入正确位置，就像整理手中的扑克牌一样。
插入排序的实现
取出元素 key = a[i]，然后将 a[0..i-1] 中每个更大的元素向右移动一个槽位，最后将 key 插入空隙。
#include <stdio.h>
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
insertion_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}在近乎有序的数据上使用插入排序
数组几乎有序时，插入排序表现出色：每个元素只需移动几个位置，复杂度接近 O(n)。这就是它被用作混合排序收尾步骤的原因。
#include <stdio.h>
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) { a[j+1] = a[j]; j--; }
a[j+1] = key;
}
}
int main(void) {
int a[] = {1, 2, 4, 3, 5}; /* one out of place */
insertion_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}稳定性
两种排序都是稳定的：相等元素会保持原有的相对顺序，因为它们只会在严格大于的比较结果下交换或移动。当按照多个键对记录排序时，稳定性十分重要。
复杂度比较
两者的平均和最坏情况复杂度都是 O(n²)，但实际表现有所不同：
- 冒泡排序：交换次数多，实际代码中很少使用
- 插入排序：写入次数更少，非常适合较小或接近有序的数组
经过优化后，两者的最佳情况都是 O(n)。
统计操作次数
让我们统计插入排序处理逆序数组时执行的比较次数，这是它的最坏情况。
#include <stdio.h>
int main(void) {
int a[] = {5, 4, 3, 2, 1};
int n = 5; long cmp = 0;
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && (cmp++, a[j] > key)) { a[j+1] = a[j]; j--; }
a[j+1] = key;
}
printf("comparisons = %ld\n", cmp);
return 0;
}快速检查
测试您对简单排序的理解。
回顾
您学会了两种简单的 O(n²) 排序算法。
- 冒泡排序在每次遍历中交换相邻元素对
- 插入排序将元素移动并插入有序区域的末尾
- 两者都是稳定的；经过优化后，在有序输入上的复杂度都能达到 O(n)
- 对于较小的数据，插入排序是更实用的选择
常见问题解答
「冒泡排序与插入排序」课时是免费的吗？
是的 — 「冒泡排序与插入排序」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 C Academy 课程的其余内容，请升级到 CoddyKit PRO。 C Academy 课程共包含 4 节课。
「冒泡排序与插入排序」这节课中我会学到什么？
简单排序 你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 C Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 C Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「冒泡排序与插入排序」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 C Academy 课中编写并运行代码吗？
能。每节 C Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。