杨校老师课堂之基于C++的排序算法详解_信息学奥赛-配套专项练习题汇总

排序算法是将一组数据按照特定顺序（如升序或降序）重新排列的算法，其核心目标是通过比较或非比较操作，使数据满足有序性要求。根据实现方式和特性，排序算法可分为以下类别：

1. 比较排序：通过元素间的比较确定顺序，理论最优时间复杂度为 O(nlog⁡n)。
   • 基础算法：选择排序、冒泡排序、插入排序。
   • 高效算法：快速排序（分治思想）、归并排序（分治与合并）、堆排序（利用堆结构）。
   • 改进算法：希尔排序（插入排序的优化）。
2. 非比较排序：不依赖元素比较，时间复杂度可达 O(n)，但适用场景有限。
   • 计数排序、基数排序、桶排序。

根据实现原理，排序算法可分为以下类别：

1. 插入类排序
   • 直接插入排序
     • 原理：将待排序元素逐个插入已排序序列的适当位置，类似整理扑克牌。
     • 时间复杂度：最好O(n)（已有序），最坏O(n²)（逆序）。
     • 稳定性：稳定。
     • 适用场景：小规模数据或基本有序的数据。
   • 希尔排序
     • 原理：改进的插入排序，通过分组（增量序列）对子序列进行插入排序，逐步缩小增量直至为1。
     • 时间复杂度：O(n log n) ~ O(n²)，取决于增量序列的选择。
     • 稳定性：不稳定。
     • 适用场景：中等规模数据。
2. 选择类排序
   • 简单选择排序
     • 原理：每次从未排序部分选择最小元素，与未排序部分的第一个元素交换。
     • 时间复杂度：O(n²)。
     • 稳定性：不稳定。
     • 适用场景：简单实现，但效率较低。
   • 堆排序
     • 原理：利用堆数据结构（完全二叉树），将数组构建为大顶堆/小顶堆，反复取堆顶元素并调整堆。
     • 时间复杂度：O(n log n)。
     • 稳定性：不稳定。
     • 适用场景：大规模数据，尤其适合动态数据流。
3. 交换类排序
   • 冒泡排序
     • 原理：重复比较相邻元素并交换顺序，使较大元素逐步“浮”到顶端。
     • 时间复杂度：最好O(n)（已有序），最坏O(n²)。
     • 稳定性：稳定。
     • 适用场景：教学或小规模数据。
   • 快速排序
     • 原理：分治法思想，选择一个基准元素，将数组分为两部分（小于基准和大于基准），递归排序子数组。
     • 时间复杂度：平均O(n log n)，最坏O(n²)（如已有序）。
     • 稳定性：不稳定。
     • 适用场景：大规模随机数据，实际应用最广泛。
4. 归并类排序
   • 归并排序
     • 原理：分治法，将数组分为两半递归排序，再合并两个有序子数组。
     • 时间复杂度：O(n log n)。
     • 稳定性：稳定。
     • 适用场景：链表排序、外部排序（如大数据文件）。
5. 基数类排序
   • 基数排序
     • 原理：按数位分配（从低位到高位），使用桶排序或计数排序对每位进行排序。
     • 时间复杂度：O(nk)（k为最大位数）。
     • 稳定性：稳定。
     • 适用场景：整数或字符串排序，位数较少时高效。
6. 其他算法
   • 计数排序：统计每个元素的出现次数，反向填充目标数组，适用于整数范围较小的情况，时间复杂度O(n+k)。
   • 桶排序：将数据分到有限数量的桶中，对每个桶单独排序，适用于均匀分布的数据。

   

• 理解基本思想：
  • 例如，插入排序通过逐个将元素插入已排序序列，快速排序通过基准值分治。
• 掌握执行过程：
  • 通过动态示意图或逐步推演，观察算法如何操作数据（如冒泡排序的相邻交换）。
• 实现代码：
  • 从简单算法（如选择排序）入手，逐步实现更复杂的算法（如归并排序）。
• 分析复杂度：
  • 对比不同算法的时间/空间复杂度（如快速排序最坏 O(n2)，平均 O(nlog⁡n)。
• 应用与优化：
  • 学习算法优化（如快速排序的三数取中法），并通过题目练习加深理解。