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

一、先解答上次的 思考题图顶点 0 1 2 3边0-1、0-2、1-2、2-3从 0 开始 BFS 典型顺序0 1 2 3二、今天学习目标了解排序算法的分类与指标掌握冒泡排序掌握选择排序掌握插入排序完整可运行代码 复杂度总结三、排序基础概念稳定排序相等元素前后顺序不变时间复杂度执行快慢空间复杂度占用额外内存多少今天这三个都是简单直观时间复杂度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八、复杂度对比表表格排序最好最坏平均稳定原地冒泡O(n)O(n²)O(n²)稳定是选择O(n²)O(n²)O(n²)不稳定是插入O(n)O(n²)O(n²)稳定是记忆口诀冒泡两两交换选择选最小放前面插入摸牌插位置九、今日小练习对数组{3, 1, 4, 2, 7, 5}分别用三种排序实现并输出结果。