这里所称的排序(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)}}# 否 排序者大概是猴子时。

Big- #{{O}}# 复杂度参考图表

Big-O 复杂度参考图表