排序算法列表

青旅半醒 2022-05-23 09:27 307阅读 0赞

## 一. 稳定的排序 ##

*  [冒泡排序][Link 1]（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(nlog n)；需要O(n)额外空间
 *  原地归并排序—O(nlog \{2\}n)如果使用最佳的现在版本
 *  二叉树排序（binary tree sort）— O(nlog n)期望时间；O(n²)最坏时间；需要 O(n)额外空间
 *  鸽巢排序（pigeonhole sort）— O(n+k)；需要O(k)额外空间
 *  基数排序（radix sort）—O(nk)；需要O(n)额外空间
 *  侏儒排序（gnome sort）—O(n²)
 *  图书馆排序（library sort）— O(nlog n)期望时间；O(n²)最坏时间；需要(1+E)n额外空间
 *  块排序（block sort）—O(nlog n)

## 二.不稳定的排序 ##

*  [选择排序][Link 2]（selection sort）—O(n²)
 *  希尔排序（shell sort）— O(nlog \{2\}n)如果使用最佳的现在版本
 *  clover排序算法（Clover sort）— O(n)期望时间，O(n²)最坏情况
 *  梳排序  O(nlog n)
 *  堆排序（heap sort）—O(nlog n)
 *  平滑排序（smooth sort）— O(nlog n)
 *  快速排序（quick sort）— O(nlog n)期望时间，O(n²)最坏情况；对于大的、随机数列表一般相信是最快的已知排序
 *  内省排序（introsort）—O(nlog n)
 *  耐心排序（patience sort）—O(nlog n+k)最坏情况时间，需要额外的O(n+k)空间，也需要找到[最长的递增子序列][Link 3]（longest increasing subsequence）

文章出处：[https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95][https_zh.wikipedia.org_wiki_E6_8E_92_E5_BA_8F_E7_AE_97_E6_B3_95]

[Link 1]: https://blog.csdn.net/cn_yefeng/article/details/80434722
[Link 2]: https://blog.csdn.net/cn_yefeng/article/details/80598370
[Link 3]: https://zh.wikipedia.org/w/index.php?title=%E6%9C%80%E9%95%B7%E7%9A%84%E9%81%9E%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97&action=edit&redlink=1
[https_zh.wikipedia.org_wiki_E6_8E_92_E5_BA_8F_E7_AE_97_E6_B3_95]: https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95