排序算法入门：冒泡、选择、插入排序详解

一、先解答上次的 思考题

图：顶点 0 1 2 3，边：0-1、0-2、1-2、2-3从 0 开始 BFS 典型顺序：0 1 2 3

二、今天学习目标

1. 了解排序算法的分类与指标
2. 掌握冒泡排序
3. 掌握选择排序
4. 掌握插入排序
5. 完整可运行代码 + 复杂度总结

三、排序基础概念

• 稳定排序：相等元素前后顺序不变
• 时间复杂度：执行快慢
• 空间复杂度：占用额外内存多少

今天这三个都是：

• 简单直观
• 时间复杂度O(n²)
• 适合小规模数据

四、1. 冒泡排序（Bubble Sort）

思想：两两比较，大的往后 “冒”，每轮冒出一个最大值。

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

五、2. 选择排序（Selection Sort）

思想：每轮选最小的，放到已排序区间末尾。

// 选择排序 void selectionSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int minIdx = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIdx]) minIdx = j; } // 交换 int temp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = temp; } }

六、3. 插入排序（Insertion Sort）

思想：像摸牌一样，把当前数插入前面已经排好的序列里。

// 插入排序 void insertionSort(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; } }

七、完整测试代码

#include <stdio.h> // 三种排序函数放这里 …… // 打印数组 void printArr(int arr[], int n) { for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); } int main() { int arr1[] = {5, 2, 9, 1, 5, 6}; int n = sizeof(arr1) / sizeof(arr1[0]); printf("原数组："); printArr(arr1, n); // 测试冒泡 bubbleSort(arr1, n); printf("冒泡排序后："); printArr(arr1, n); return 0; }

运行结果

原数组：5 2 9 1 5 6 冒泡排序后：1 2 5 5 6 9

八、复杂度对比表

表格

记忆口诀：

• 冒泡：两两交换
• 选择：选最小放前面
• 插入：摸牌插位置

九、今日小练习

对数组{3, 1, 4, 2, 7, 5}分别用三种排序实现并输出结果。