【Unity小白学习日记2】数据结构必考知识点 | 冒泡、选择、插入排序

1、冒泡排序

核心思路描述

重复遍历数组，相邻两个元素两两比较，前大于后就交换。每一轮会把未排序区间最大元素 “冒泡” 到末尾。增加交换标记优化，如果一轮没有发生交换，说明数组已经有序，可以直接结束。

关键 C# 代码

// 冒泡排序 从小到大 public void BubbleSort(int[] arr) { if(arr == null || arr.Length <= 1) return; int n = arr.Length; for(int i = 0; i < n - 1; i++) { bool swapFlag = false; // 交换标记，优化 // 后面i个元素已经排好，不用比较 for(int j = 0; j < n - 1 - i; j++) { if(arr[j] > arr[j+1]) { // 交换 int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; swapFlag = true; } } if(!swapFlag) break; // 没有交换，直接退出 } }

总结：

冒泡排序，就是循环遍历数组，相邻元素两两对比，如果前面的数字比后面大就交换。每一轮遍历，会把未排序部分最大的元素移动到数组末尾。最多执行 n‑1 轮。我加了一个交换标记做优化，如果某一轮一次交换都没有发生，代表数组已经全部有序，可以直接跳出循环。最坏时间复杂度 O (n²)，是原地、稳定排序。

2、选择排序

核心思路描述

将数组分成已排序区间、未排序区间。每一轮在未排序区间找到最小值的下标，把最小值和未排序区间第一个位置做交换，不断扩大已排序区间。

关键代码片段

public void SelectSort(int[] arr) { int n = arr.Length; for(int i = 0; i < n - 1; i++) { int minIndex = i; // 记录最小值下标 // 在未排序区找最小下标 for(int j = i + 1; j < n; j++) { if(arr[j] < arr[minIndex]) minIndex = j; } // 和未排序第一个位置交换 int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } }

总结：

选择排序把数组划分成已排序和未排序两部分。每一轮在未排序区间找到最小值的索引，和未排序的第一个元素交换位置。循环完成排序。时间复杂度固定 O (n²)，原地排序，属于不稳定排序。

3、插入排序

核心思路描述

类似整理扑克牌。数组前面部分作为已经有序的序列，依次取出后面未排序的元素，向前和有序部分对比，把更大的元素向后挪，将当前元素插入到合适位置。数组接近有序时效率很高。

关键代码片段

public void InsertSort(int[] arr) { int n = arr.Length; for(int i = 1; i < n; i++) { int cur = arr[i]; // 当前待插入元素 int j = i - 1; // 向前遍历有序区间，大于cur的全部后移 while(j >= 0 && arr[j] > cur) { arr[j+1] = arr[j]; j--; } arr[j+1] = cur; // 插入到空位 } }

总结：

插入排序就像整理手牌。把数组前面当作已经有序，依次拿后面每一个元素，向前比较，把比它大的元素往后挪，找到空位插入。当原数组本身比较有序的时候，它的效率会很好。最坏时间复杂度 O (n²)，原地、稳定排序。

三者对比速记

✨小何同学：路漫漫其修远兮，吾将上下而求索！✨