这里所称的排序(Sorting),是指将一串不规则的串行数据(如数组数据)依照递增或是递减的方式重新编排。要将一串不规则的数值数据递增或是递减排列,方法当然不会只有一种,而不同方法排列数据的难易度、速度和其它特性自然也会有所不同。排序算法(Sorting Algorithm)就是排列数据的方法,目前已知的方法有很多,在这篇文章中将会整理本站所介绍过的大部份排序算法。
一般排序算法
这边所列表出来的算法都是用来以递增或递减的方式排序一个串行。
以 #{{n}}# 来表示要排序的数据笔数。以 #{{k}}# 来表示要排序的数据可能的值的数量。以 #{{m}}# 来表示桶子的数量。
| 算法 | 最差时间复杂度 | 最佳时间复杂度 | 平均时间复杂度 | 最差空间复杂度 | 是否稳定 | 应用场合 |
|---|---|---|---|---|---|---|
| 选择排序 Selection Sort |
#{{O(n^2)}}# | #{{O(n^2)}}# | #{{O(n^2)}}# | #{{O(1)}}# | 否 | 不怎么实用。 |
| 交换排序 Exchange Sort |
#{{O(n^2)}}# | #{{O(n^2)}}# | #{{O(n^2)}}# | #{{O(1)}}# | 否 | 不怎么实用。 |
| 冒泡排序 Bubble Sort |
#{{O(n^2)}}# | #{{O(n)}}# | #{{O(n^2)}}# | #{{O(1)}}# | 是 | 当 #{{n}}# 很小时特别适用。 |
| 插入排序 Insertion Sort |
#{{O(n^2)}}# | #{{O(n)}}# | #{{O(n^2)}}# | #{{O(1)}}# | 是 | 当 #{{n}}# 很小时特别适用。也常用来加速快速排序法和合并排序法。 |
| 鸡尾酒排序 Cocktail Sort |
#{{O(n^2)}}# | #{{O(n)}}# | #{{O(n^2)}}# | #{{O(1)}}# | 是 | 不怎么实用。 |
| 希尔排序 Shell Sort |
#{{O(n^2)}}# | #{{O(n \log n)}}# | ? | #{{O(1)}}# | 否 | 如果能找出最佳间距(gap),是不错的选择;但若找不出最佳间距(gap)的话,就不怎么实用。 |
| 合并排序 Merge Sort |
#{{O(n \log n)}}# | #{{O(n \log n)}}# | #{{O(n \log n)}}# | #{{O(n)}}# | 是 | 适用于大部分的场合。 |
| 快速排序 Quick Sort |
#{{O(n^2)}}# | #{{O(n \log n)}}# | #{{O(n \log n)}}# | 一般:#{{O(n)}}# | 否 | 适用于大部分不需稳定排序的场合。 |
| 堆积排序 Heap Sort |
#{{O(n \log n)}}# | #{{O(n)}}# | #{{O(n \log n)}}# | #{{O(1)}}# | 否 | 不怎么实用。 |
| 计数排序 Counting Sort |
#{{O(n + k)}}# | #{{O(n + k)}}# | #{{O(n + k)}}# | 原地:#{{O(k)}}# 非原地:#{{O(n + k)}}# |
原地:否 非原地:是 |
#{{k}}# 愈小愈适用。 |
| 桶排序 Bucket Sort |
#{{O(n^2)}}# | #{{O(n + m)}}# | #{{O(n + {{n^2} \over m} + m )}}# | 不预先配置桶子的空间:#{{O(n + k)}}# 预先配置桶子的空间:#{{O(n \times k)}}# 使用了其它需要额外空间的排序算法:? |
使用稳定排序法来排序每个桶子:是 有使用到不稳定排序法:否 |
数据可以被有效哈希时适用。 |
| 基数排序 Radix Sort |
LSD:#{{O((n + k) \times d)}}# 稳定 MSD:#{{O(n \times d)}}# |
LSD:#{{O((n + k) \times d)}}# 稳定 MSD:#{{O(n)}}# |
LSD:#{{O((n + k) \times d)}}# 稳定 MSD:#{{O(n \times d)}}# |
LSD:#{{O(n + k)}}# 稳定 MSD:#{{O((n + k) \times d)}}# |
LSD:是 稳定 MSD:是 (原地 MSD:否) |
数据可以被快速切分为多键值时适用。 |
特殊排序算法
排名搜索算法
在串行中快速找出第 #{{K}}# 小或是第 #{{K}}# 大的元素。
以 #{{n}}# 来表示要搜索或排序的数据笔数。
| 算法 | 最差时间复杂度 | 最佳时间复杂度 | 平均时间复杂度 | 最差空间复杂度 | 是否稳定 | 应用场合 |
|---|---|---|---|---|---|---|
| 快速选择 Quickselect |
#{{O(n^2)}}# | #{{O(n)}}# | #{{O(n)}}# | #{{O(1)}}# | 否 | 想从串行中找出一个第 K 小或是第 K 大元素时。 |
乱排算法
用很奇葩的作法,以递增或递减的方式排序一个串行。
以 #{{n}}# 来表示要搜索或排序的数据笔数。
| 算法 | 最差时间复杂度 | 最佳时间复杂度 | 平均时间复杂度 | 最差空间复杂度 | 是否稳定 | 应用场合 |
|---|---|---|---|---|---|---|
| Bogo 排序 Bogo Sort |
#{{O(\infty)}}# | #{{O(n)}}# | #{{O({n \times n!})}}# | #{{O(1)}}# | 否 | 排序者大概是猴子时。 |

