排序算法是将一组数据按照特定顺序（如升序或降序）重新排列的算法，其核心目标是通过比较或非比较操作，使数据满足有序性要求。根据实现方式和特性，排序算法可分为以下类别：
- 比较排序：通过元素间的比较确定顺序，理论最优时间复杂度为 O(nlogn)。
- 基础算法：选择排序、冒泡排序、插入排序。
- 高效算法：快速排序（分治思想）、归并排序（分治与合并）、堆排序（利用堆结构）。
- 改进算法：希尔排序（插入排序的优化）。
- 非比较排序：不依赖元素比较，时间复杂度可达 O(n)，但适用场景有限。
- 计数排序、基数排序、桶排序。
根据实现原理，排序算法可分为以下类别：
- 插入类排序
- 直接插入排序
- 原理：将待排序元素逐个插入已排序序列的适当位置，类似整理扑克牌。
- 时间复杂度：最好O(n)（已有序），最坏O(n²)（逆序）。
- 稳定性：稳定。
- 适用场景：小规模数据或基本有序的数据。
- 希尔排序
- 原理：改进的插入排序，通过分组（增量序列）对子序列进行插入排序，逐步缩小增量直至为1。
- 时间复杂度：O(n log n) ~ O(n²)，取决于增量序列的选择。
- 稳定性：不稳定。
- 适用场景：中等规模数据。
- 直接插入排序
- 选择类排序
- 简单选择排序
- 原理：每次从未排序部分选择最小元素，与未排序部分的第一个元素交换。
- 时间复杂度：O(n²)。
- 稳定性：不稳定。
- 适用场景：简单实现，但效率较低。
- 堆排序
- 原理：利用堆数据结构（完全二叉树），将数组构建为大顶堆/小顶堆，反复取堆顶元素并调整堆。
- 时间复杂度：O(n log n)。
- 稳定性：不稳定。
- 适用场景：大规模数据，尤其适合动态数据流。
- 简单选择排序
- 交换类排序
- 冒泡排序
- 原理：重复比较相邻元素并交换顺序，使较大元素逐步“浮”到顶端。
- 时间复杂度：最好O(n)（已有序），最坏O(n²)。
- 稳定性：稳定。
- 适用场景：教学或小规模数据。
- 快速排序
- 原理：分治法思想，选择一个基准元素，将数组分为两部分（小于基准和大于基准），递归排序子数组。
- 时间复杂度：平均O(n log n)，最坏O(n²)（如已有序）。
- 稳定性：不稳定。
- 适用场景：大规模随机数据，实际应用最广泛。
- 冒泡排序
- 归并类排序
- 归并排序
- 原理：分治法，将数组分为两半递归排序，再合并两个有序子数组。
- 时间复杂度：O(n log n)。
- 稳定性：稳定。
- 适用场景：链表排序、外部排序（如大数据文件）。
- 归并排序
- 基数类排序
- 基数排序
- 原理：按数位分配（从低位到高位），使用桶排序或计数排序对每位进行排序。
- 时间复杂度：O(nk)（k为最大位数）。
- 稳定性：稳定。
- 适用场景：整数或字符串排序，位数较少时高效。
- 基数排序
- 其他算法
- 计数排序：统计每个元素的出现次数，反向填充目标数组，适用于整数范围较小的情况，时间复杂度O(n+k)。
- 桶排序：将数据分到有限数量的桶中，对每个桶单独排序，适用于均匀分布的数据。
- 理解基本思想：
- 例如，插入排序通过逐个将元素插入已排序序列，快速排序通过基准值分治。
- 掌握执行过程：
- 通过动态示意图或逐步推演，观察算法如何操作数据（如冒泡排序的相邻交换）。
- 实现代码：
- 从简单算法（如选择排序）入手，逐步实现更复杂的算法（如归并排序）。
- 分析复杂度：
- 对比不同算法的时间/空间复杂度（如快速排序最坏 O(n2)，平均 O(nlogn)。
- 应用与优化：
- 学习算法优化（如快速排序的三数取中法），并通过题目练习加深理解。
- 学习算法优化（如快速排序的三数取中法），并通过题目练习加深理解。
以下排序算法的题目题号，涵盖模板题、应用题及变形题，总计 23 道：
- 模板与基础题
- P1177 【模板】快速排序（验证算法效率）
- P1059 明明的随机数（排序+去重）
- P1012 拼数（自定义字符串排序规则）
- P1104 生日（结构体多关键字排序）
- P1908 逆序对（归并排序应用）
- 应用题与变形题
- P1093 奖学金（多条件排序）
- P1068 分数线划定（排序后截取区间）
- P1116 车厢重组（冒泡排序交换次数统计）
- P1774 最接近神的人（逆序对问题）
- P1923 求第k小的数（快速选择算法）
- P1781 总统选举（排序应用）
- P1285 队员分组（排序与分组逻辑）
- P1212 铺放矩形块（几何排序问题）
- P2023 维护序列（排序与数据维护）
- 其他相关题目
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
