数据结构：嵌入式常用排序与查找算法精讲-编程实验室

这章讲解了，嵌入式当中，数据结构得到基本排序和查找算法，排序有冒泡排序，选择排序，插入排序，希尔排序，快速排序，查找算法便是二分查找（折半查找）。

在嵌入式开发中，数据是核心。排序让无序数据变有序，查找让目标数据快速定位。本章聚焦嵌入式最常用的排序冒泡、选择、插入、希尔、快速排序，及查找二分查找，结合生活类比与代码实战，助你轻松掌握。

一、排序算法基础认知

排序是将一组数据按特定顺序（升序/降序）排列。嵌入式场景中，排序常用于数据显示（如传感器数据排序后取中值滤波）、资源调度（按优先级排序任务）。算法效率看时间复杂度（执行步数）和空间复杂度（额外内存），嵌入式资源有限，需按需选择。

二、冒泡排序 Bubble Sort

知识点

核心思想像水中气泡上浮，重复遍历数组，每次比较相邻元素，逆序则交换。每轮将最大元素“浮”到末尾，n个元素需n-1轮。

时间复杂度最好On（已排序，加优化可提前退出），最坏On²（逆序），平均On²。

空间复杂度 O1（原地排序）。

稳定性稳定（相等元素不交换顺序）。

代码实现

int BubbleSort(int *pArray, int Len) { int i = 0; int j = 0; int Tmp = 0; for (j = 0; j < Len-1; j++) { for (i = 0; i < Len-1-j; i++) { if (pArray[i] > pArray[i+1]) { Tmp = pArray[i]; pArray[i] = pArray[i+1]; pArray[i+1] = Tmp; } } } return 0; }

三、选择排序 Selection Sort

知识点

核心思想每轮从待排序区选最小元素，放到已排序区末尾。像挑苹果，每次选最小放筐里。

时间复杂度无论好坏均On²（固定n-1轮，每轮找最小）。

空间复杂度 O1（原地）。

稳定性不稳定（如[2,2,1]，首2会与1交换，次2前移，顺序变）。

代码实现

int SelectSort(int *pArray, int Len) { int j = 0; int i = 0; int Min = 0; int Tmp = 0; for (j = 0; j < Len-1; j++) { Min = j; for (i = j+1; i < Len; i++) { if (pArray[i] < pArray[Min]) { Min = i; } } if (Min != j) { Tmp = pArray[j]; pArray[j] = pArray[Min]; pArray[Min] = Tmp; } } return 0; }

四、插入排序 Insertion Sort

知识点

核心思想像整理扑克牌，将未排序元素逐个插入已排序区正确位置。已排序区初始只有首元素。

时间复杂度最好O1（已排序，只需比较不移动），最坏On²（逆序），平均On²。

空间复杂度 O1（原地）。

稳定性稳定（插入时遇相等元素停，不后移）。

代码实现

int InsertSort(int *pArray, int Len) { int j = 0; int i = 0; int Tmp = 0; for (j = 1; j < Len; j++) { Tmp = pArray[j]; for (i = j; i > 0 && pArray[i-1] > Tmp; i--) { pArray[i] = pArray[i-1]; } pArray[i] = Tmp; } return 0; }

五、希尔排序 Shell Sort

知识点

核心思想插入排序改进版，先按间隔gap分组（如gap=n/2, n/4...1），每组内插入排序，最后gap=1时整体插入排序。小数据量时高效，大数据量比O(n²)快。

时间复杂度依赖gap序列，平均约On^1.3，最坏On²。

空间复杂度 O1。

稳定性不稳定（分组交换可能打乱相等元素顺序）。

代码实现

int ShellSort(int *pArray, int Len) { int step = 0; int j = 0; int i = 0; int Tmp = 0; for (step = Len / 2; step > 0; step /= 2) { for (j = step; j < Len; j++) { Tmp = pArray[j]; for (i = j; i > step-1 && pArray[i-step] > Tmp; i -= step) { pArray[i] = pArray[i-step]; } pArray[i] = Tmp; } } return 0; }

六、快速排序 Quick Sort

知识点

核心思想分治法，选基准pivot，将数组分两部分左边≤pivot右边≥pivot，递归排左右子数组。嵌入式常用高效排序。

时间复杂度最好O(nlogn)（基准分均匀），最坏On²（基准选两端且数组有序），平均O(nlogn)。

空间复杂度 O(logn)（递归栈，最坏On）。

稳定性不稳定（交换基准时可能打乱顺序）。

代码实现

int QuickSort(int *pArray, int Low, int High) { int i = 0; int j = 0; int key = 0; key = pArray[Low]; j = High; i = Low; while (i < j) { while (i < j && pArray[j] >= key) { j--; } pArray[i] = pArray[j]; while (i < j && pArray[i] <= key) { i++; } pArray[j] = pArray[i]; } pArray[i] = key; if (Low < i-1) { QuickSort(pArray, Low, i-1); } if (i+1 < High) { QuickSort(pArray, i+1, High); } return 0; }

七、二分查找 Binary Search（折半查找）

知识点

核心思想仅适用于有序数组！每次取中间元素比较，相等则找到；目标小则查左半区，大则查右半区，重复至区间为空。

时间复杂度 O(logn)（每次减半查找范围）。

空间复杂度 O1（循环版）或O(logn)（递归版）。

代码实现

int MidSearch(int *pArray, int Low, int High, int TmpData) { int Mid = 0; if (High < Low) { return -1; } Mid = (Low + High) / 2; if (pArray[Mid] > TmpData) { return MidSearch(pArray, Low, Mid-1, TmpData); } else if (pArray[Mid] < TmpData) { return MidSearch(pArray, Mid+1, High, TmpData); } else if (pArray[Mid] == TmpData) { return Mid; } }