1.2 数组排序

1.2 数组排序

数组排序是计算机科学中最基本的问题之一。排序算法有很多种，每种算法都有其特点和适用场景。

1. 排序算法的分类

排序算法可以按照不同的标准进行分类：

1. 按照时间复杂度分类：

   • 简单排序算法：时间复杂度为 $O(n^2)$，如冒泡排序、选择排序、插入排序
   • 高级排序算法：时间复杂度为 $O(n \log n)$，如快速排序、归并排序、堆排序
   • 线性排序算法：时间复杂度为 $O(n)$，如计数排序、桶排序、基数排序

2. 按照空间复杂度分类：

   • 原地排序算法：空间复杂度为 $O(1)$，如冒泡排序、选择排序、插入排序、快速排序、堆排序
   • 非原地排序算法：空间复杂度为 $O(n)$，如归并排序、计数排序、桶排序、基数排序

3. 按照稳定性分类：

   • 稳定排序算法：相等元素的相对顺序在排序后保持不变，如冒泡排序、插入排序、归并排序、计数排序、桶排序、基数排序
   • 不稳定排序算法：相等元素的相对顺序在排序后可能改变，如选择排序、快速排序、堆排序

2. 排序算法的评价指标

评价一个排序算法的好坏，主要从以下几个方面考虑：

1. 时间复杂度：算法执行所需的时间
2. 空间复杂度：算法执行所需的额外空间
3. 稳定性：相等元素的相对顺序是否保持不变
4. 原地性：是否需要在原数组之外开辟额外空间
5. 自适应性：算法是否能够利用输入数据的特性来提高效率

3. 常见排序算法

常见的排序算法包括：

1. 冒泡排序：通过相邻元素比较和交换，将最大元素逐步"冒泡"到数组末尾
2. 选择排序：每次从未排序区间选择最小元素，放到已排序区间末尾
3. 插入排序：将未排序区间的元素插入到已排序区间的合适位置
4. 快速排序：选择一个基准元素，将数组分为两部分，递归排序
5. 归并排序：将数组分成两半，分别排序后合并
6. 堆排序：利用堆这种数据结构进行排序
7. 计数排序：统计每个元素出现的次数，按顺序输出
8. 桶排序：将元素分到有限数量的桶中，对每个桶单独排序
9. 基数排序：按照元素的位数进行排序

4. 排序算法的选择

在实际应用中，选择合适的排序算法需要考虑以下因素：

1. 数据规模：小规模数据可以使用简单排序算法，大规模数据需要使用高级排序算法
2. 数据特征：如果数据基本有序，插入排序效率较高；如果数据分布均匀，快速排序效率较高
3. 空间限制：如果空间有限，应该选择原地排序算法
4. 稳定性要求：如果需要保持相等元素的相对顺序，应该选择稳定排序算法
5. 硬件环境：不同的硬件环境可能适合不同的排序算法