排序算法分类

稳定的
冒泡排序（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 sort）— O(n2)
图书馆排序（library sort）— O(n log n) with high probability,需要(1+ε)n额外空间
不稳定
选择排序（selection sort）—O(n2)
希尔排序（shell sort）—O(n log n)如果使用最佳的现在版本
组合排序— O(n log n)
堆排序（heap sort）—O(n log n)
平滑排序（smooth sort）— O(n log n)
快速排序（quick sort）—O(n log n)期望时间, O(n2)最坏情况;对于大的、乱数列表一般相信是最快的已知排序
内省排序（introsort）—O(n log n)
耐心排序（patience sort）—O(n log n + k)最坏情况时间，需要额外的O(n + k)空间，也需要找到最长的递增子串行（longest increasing subsequence）
不实用的排序算法
Bogo排序— O(n × n!)，最坏的情况下期望时间为无穷。
Stupid排序—O(n3);递归版本需要O(n2)额外存储器
珠排序（bead sort）— O(n) or O(√n),但需要特别的硬件
Pancake sorting—O(n),但需要特别的硬件
臭皮匠排序（stooge sort）算法简单，但需要约n^2.7的时间