当前位置：首页 > news >正文

速成蓝桥杯之排序（一）

news 2026/5/7 19:46:24

一、冒泡排序（Bubble Sort）

核心思想：重复遍历待排序序列，依次比较相邻元素，若顺序错误则交换，使较大元素逐步 "冒泡" 至末尾。

时间复杂度：平均 / 最坏 O(n2)，最好 O(n)（优化后）
空间复杂度：O(1)
稳定性：稳定

解题步骤

从数组首元素开始，比较相邻两元素，前 > 后则交换。
每轮遍历确定当前最大元素位置，下一轮减少一次比较。
若某轮无交换，说明已有序，可提前结束。

蓝桥常考：基础排序实现、时间复杂度分析、稳定性判断。

二、选择排序（Selection Sort）

核心思想：每轮选未排序区最小（大）元素，放至已排序区末尾。

时间复杂度：平均 / 最坏 / 最好 O(n2)
空间复杂度：O(1)
稳定性：不稳定

解题步骤

设首元素为最小值，遍历后续找更小值并记录下标。
遍历结束，将最小值与未排序区首元素交换。
缩小未排序区间，重复至全部有序。

蓝桥常考：与冒泡 / 插入对比、交换次数、稳定性辨析。

三、插入排序（Insertion Sort）

核心思想：将未排序元素逐个插入已排序序列对应位置。

时间复杂度：平均 / 最坏 O(n2)，最好 O(n)（基本有序）
空间复杂度：O(1)
稳定性：稳定

解题步骤

首元素视为已排序，从第 2 个元素开始。
取当前元素，向前扫描已排序区，大于当前值则后移。
找到合适位置插入，直至全部处理。

蓝桥常考：近乎有序数据、小规模数据、作为高级排序优化（如快排、归并）。

四、归并排序（Merge Sort）

核心思想：分治法 —— 递归拆分至单元素，再两两合并有序序列。

时间复杂度：平均 / 最坏 / 最好 O(nlogn)
空间复杂度：O(n)
稳定性：稳定

解题步骤

分解：将数组二分，递归拆分至长度 1。
合并：双指针遍历两有序子数组，取小元素放入结果。
复制剩余：处理任一子数组剩余元素。

蓝桥常考：逆序对统计（高频）、外部排序、分治思想、大数据量稳定排序。

五、快速排序（Quick Sort）

核心思想：分治法 —— 选基准值，分区（小左大右），递归排序子区间。

时间复杂度：平均 O(nlogn)，最坏 O(n2)（已序 / 逆序）
空间复杂度：O(logn)（递归栈）
稳定性：不稳定

解题步骤

选基准：随机 / 三数取中选 pivot。
分区：遍历数组，小于 pivot 放左，大于放右。
递归：对左右子数组重复上述步骤。

蓝桥常考：手写快排、第 K 大 / 小数（Partition）、大数据量排序、复杂度优化。

六、堆排序（Heap Sort）

核心思想：利用完全二叉树的堆结构，建堆后反复取堆顶并调整。

时间复杂度：平均 / 最坏 / 最好 O(nlogn)
空间复杂度：O(1)
稳定性：不稳定

解题步骤

建堆：从最后非叶节点向前调整，构建最大 / 最小堆。
交换：堆顶与末尾元素交换，确定最大元素位置。
调整：堆大小减 1，重新调整堆，重复至有序。

蓝桥常考：TopK 问题、优先级队列、海量数据前 N 大、时间复杂度。

七、桶排序（Bucket Sort）

核心思想：按值范围分桶，桶内排序后合并。

时间复杂度：平均 O(n+k)，最坏 O(n2)
空间复杂度：O(n+k)
稳定性：稳定（桶内用稳定排序）

解题步骤

分桶：确定桶数与区间，映射元素至对应桶。
桶内排序：对非空桶用插入 / 快排等。
合并：按桶序输出所有元素。

蓝桥常考：均匀分布数据、浮点数排序、频率统计、空间换时间。

八、基数排序（Radix Sort）

核心思想：按低位到高位（或反向）逐位用稳定排序（如桶 / 计数）。

时间复杂度：O(d×(n+k))（d 为位数，k 为基数）
空间复杂度：O(n+k)
稳定性：稳定

解题步骤

取位：从最低位开始，取当前位数字。
分桶：按位值入对应桶（0~9）。
收集：按桶序收集，处理更高位，直至最高位。

蓝桥常考：整数 / 字符串排序、大数据量线性时间、位数相关问题。

九、常考题型汇总

基础实现：手写冒泡 / 选择 / 插入 / 快排 / 归并。
特性辨析：时间 / 空间复杂度、稳定性、适用场景对比。
经典应用
- 归并：逆序对（高频）、外部排序
- 快排：第 K 大 / 小、区间排序
- 堆：TopK、优先级队列
- 桶 / 基数：频率统计、大数据线性排序
综合题：排序 + 二分、贪心、DP、字符串处理。