分类

在计算机科学所使用的排序算法通常被分类为：

计算的时间复杂度（最差、平均、和最好性能），依据列表（list）的大小( n )。一般而言，好的性能是O( n log n )，且坏的性能是O( n )。对于一个排序理想的性能是O( n )。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要O( n log n )。

内存使用量（以及其他电脑资源的使用）

稳定性： 稳定排序算法 会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是 稳定 的，当有两个相等键值的纪录 R 和 S ，且在原本的列表中 R 出现在 S 之前，在排序过的列表中 R 也将会是在 S 之前。

依据排序的方法：插入、交换、选择、合并等等。

稳定性

当相等的元素是无法分辨的，比如像是整数，稳定性并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。

在这个状况下，有可能产生两种不同的结果，一个是让相等键值的纪录维持相对的次序，而另外一个则没有：

不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地实现为稳定。作这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个对象间之比较，（比如上面的比较中加入第二个标准：第二个键值的大小）就会被决定使用在原先数据次序中的条目，当作一个同分决赛。然而，要记住这种次序通常牵涉到额外的空间负担。

排序算法列表

在这个表格中， n 是要被排序的纪录数量以及 k 是不同键值的数量。

稳定的排序

冒泡排序（bubble sort）— O( n )

插入排序（insertion sort）—O( n )

鸡尾酒排序（cocktail sort）—O( n )

桶排序（bucket sort）—O( n )；需要O( k )额外空间

计数排序（counting sort）—O( n + k )；需要O( n + k )额外空间

归并排序（merge sort）—O( n log n )；需要O( n )额外空间

原地归并排序— O( n log n )如果使用最佳的现在版本

二叉排序树排序（binary tree sort）— O( n log n )期望时间；O( n )最坏时间；需要O( n )额外空间

鸽巢排序（pigeonhole sort）—O( n + k )；需要O( k )额外空间

基数排序（radix sort）—O( n · k )；需要O( n )额外空间

侏儒排序 （ 英语 ： Gnome sort ） （gnome sort）— O( n )

图书馆排序（library sort）— O( n log n )期望时间；O( n )最坏时间；需要(1+ε) n 额外空间

块排序 （ 英语 ： Block sort ） （block sort）— O( n log n )

不稳定的排序

选择排序（selection sort）—O( n )

希尔排序（shell sort）—O( n log n )如果使用最佳的现在版本

Clover排序算法（Clover sort）—O(n)期望时间，O(n )最坏情况

梳排序— O( n log n )

堆排序（heap sort）—O( n log n )

平滑排序（smooth sort）— O( n log n )

快速排序（quick sort）—O( n log n )期望时间，O( n )最坏情况；对于大的、随机数列表一般相信是最快的已知排序

内省排序（introsort）—O( n log n )

耐心排序（patience sort）—O( n log n + k )最坏情况时间，需要额外的O( n + k )空间，也需要找到最长的递增子序列（longest increasing subsequence）

不实用的排序

Bogo排序— O( n × n !)，最坏的情况下期望时间为无穷。

Stupid排序—O( n );递归版本需要O( n )额外内存

珠排序（bead sort）— O( n ) or O(√ n ),但需要特别的硬件

煎饼排序 （ 英语 ： Pancake sorting ） —O( n ),但需要特别的硬件

臭皮匠排序（stooge sort）算法简单，但需要约n^2.7的时间

简要比较

均按从小到大排列

k代表数值中的"数位"个数

n代表数据规模

m代表数据的最大值减最小值

参考文献

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。