排序算法

排序是计算机科学中最基础也最重要的操作之一。本部分涵盖八大经典排序算法，从简单的 $O(n^2)$ 算法到高效的 $O(n\log n)$ 算法，再到非比较型的基数排序，帮助理解不同排序策略的设计思想、时间复杂度与适用场景。

内容导航

• 冒泡排序

  通过相邻元素比较交换实现，稳定排序，时间复杂度为 $O(n^2)$。

• 选择排序

  每轮选取最小元素放到已排序区间末尾，不稳定，时间复杂度为 $O(n^2)$。

• 插入排序

  逐个将元素插入已排序序列正确位置，稳定排序，时间复杂度为 $O(n^2)$。

• 希尔排序

  基于插入排序的分组增量改进。

• 快速排序

  基于分治的哨兵划分策略，平均时间复杂度为 $O(n\log n)$。

• 归并排序

  基于分治的划分合并策略，稳定排序，时间复杂度为 $O(n\log n)$。

• 堆排序

  利用堆数据结构实现，原地排序，时间复杂度为 $O(n\log n)$。

• 基数排序

  非比较型排序，按位计数分配回收。

• 综合项目

  卡牌对战游戏：排序与牌局调度系统综合实践。