排序算法 汇总 【笔记】

序算法汇总 这里记录一下各种排序算法的比较和特性，主要摘自维基百科 稳定的

冒泡排序（bubble sort） — O(n2)
鸡尾酒排序 (Cocktail sort, 双向的冒泡排序) — O(n2)
插入排序 （insertion sort）— O(n2)
桶排序 （bucket sort）— O(n); 需要 O(k) 额外空间
计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外空间
合并排序 （merge sort）— O(n log n); 需要 O(n) 额外空间
原地合并排序 — O(n2)
二叉排序树排序 （Binary tree sort） — O(n log n)期望时间; O(n2)最坏时间; 需要 O(n) 额外空间
鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 额外空间
基数排序 （radix sort）— O(n·k); 需要 O(n) 额外空间
Gnome 排序 — O(n2)
图书馆排序 — O(n log n) with high probability, 需要 (1+ε)n 额外空间

不稳定

选择排序 （selection sort）— O(n2)
希尔排序 （shell sort）— O(n log n) 如果使用最佳的现在版本
组合排序 — O(n log n)
堆排序 （heapsort）— O(n log n)
平滑排序 — O(n log n)
快速排序 （quicksort）— O(n log n) 期望时间, O(n2) 最坏情况; 对于大的、乱数列表一般相信是最快的已知排序
Introsort — O(n log n)
Patience sorting — O(n log n + k) 最坏情况时间，需要 额外的 O(n + k) 空间，也需要找到最长的递增子串行（longest increasing subsequence）

不实用的排序算法

Bogo排序 — O(n × n!)，最坏的情况下期望时间为无穷。
Stupid sort — O(n3); 递归版本需要 O(n2) 额外存储器
珠排序（Bead sort） — O(n) or O(√n), 但需要特别的硬件
Pancake sorting — O(n), 但需要特别的硬件

平均时间复杂度

平均时间复杂度由高到低为：

冒泡排序 O(n2)
插入排序 O(n2)
选择排序 O(n2)
归并排序 O(n log n)
堆排序 O(n log n)
快速排序 O(n log n)
希尔排序 O(n1.25)
基数排序 O(n)

说明：虽然完全逆序的情况下，快速排序会降到选择排序的速度，不过从概率角度来说(参考信息学理论，和概率学)，不对算法做编程上优化时，快速排序的平均速度比堆排序要快一些。 实际测试结果

原文地址：http://www.cnblogs.com/whoamme/archive/2013/01/23/2874089.html