排序算法

很多排序算法，整理一下。

1.效率低下的算法
bogo sort 博戈排序，又称stupid sort，slow sort，猴子排序 （随机交换位置直到有序）
bead sort 珠排序 （排好珠子，然后靠重力珠子下落，瞬间完成排序，但计算机上无法实现）
pancake sort 煎饼排序

2.稳定的算法
冒泡排序（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额外空间

3.不稳定的算法
选择排序（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)最坏情况;对于大的、乱数列表一般相信是最快的已知排序

可以参考维基百科上的资料，相当详细
http://en.wikipedia.org/wiki/List_of_algorithms#Sequence_sorting
http://en.wikipedia.org/wiki/Sorting_algorithms
http://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95