排序

概述

排序是将一组数据按关键字升序或降序排列的过程，关注时间复杂度与稳定性。

分类

• 内部排序：数据能全部放入内存中处理。
• 外部排序：数据规模较大，需要借助外存。
• 比较类排序：通过关键字比较完成排序。
• 非比较类排序：利用数据特性完成排序（如计数、桶、基数）。

常见排序算法

• 插入排序、希尔排序。
• 选择排序、堆排序。
• 冒泡排序。
• 快速排序、归并排序。
• 计数排序、桶排序、基数排序。

常见指标

• 时间复杂度：最好、平均、最坏情况。
• 空间复杂度：是否需要额外空间。
• 稳定性：相同关键字的相对次序是否保持不变。