排序算法是计算机科学中的一类算法，用于将一系列对象（通常是数字、字符串或记录）根据一定的顺序进行排列。排序算法可以按照不同的标准对元素进行排序，最常见的是按照数字顺序或字典顺序。

主要特点

  1. 目的：将一组数据元素按照特定的顺序排列。
  2. 顺序：可以是升序（从小到大）或降序（从大到小）。
  3. 效率：算法的效率通常由其时间复杂度和空间复杂度来衡量。
  4. 稳定性：稳定的排序算法保证了相等的元素在排序后不会改变它们的相对顺序。

分类

  1. 比较类排序：通过比较元素的值来决定它们的顺序，如快速排序、归并排序、冒泡排序等。
  2. 非比较类排序：不通过比较元素的值，而是通过其他方式（如元素的键值）来排序，如计数排序、基数排序等。

常见的排序算法

排序算法 平均时间复杂度 最坏时间复杂度 最好时间复杂度 备注
计数排序 O(n + k) O(n + k) O(n + k) k是范围，n是数量
基数排序 O(nk) O(nk) O(nk) k是最大数位数
桶排序 O(n + k) O(n^2) O(n + k) k是桶的数量
组合排序 O(n^2) O(n^2) O(n) 减少冒泡排序的交换次数
希尔排序 取决于间隔序列 O(n^2) 取决于间隔序列 间隔序列影响性能
插入排序 O(n^2) O(n^2) O(n) 适合小数据集或部分有序数据
选择排序 O(n^2) O(n^2) O(n^2) 无论数组初始状态如何，时间复杂度不变
鸡尾酒排序 O(n^2) O(n^2) O(n) 双向冒泡排序
冒泡排序 O(n^2) O(n^2) O(n) 适合小数据集
快速排序 O(n log n) O(n^2) O(n log n) 依赖于基准的选择
归并排序 O(n log n) O(n log n) O(n log n) 稳定排序
堆排序 O(n log n) O(n log n) O(n log n)