几大排序算法比较：

比较排序包括：

• 快速排序
• 堆排序
• 归并排序
• 插入排序
• 选择排序
• 冒泡排序

非比较排序包括：

• 基数排序
• 计数排序
• 桶排序

稳定的排序

• 冒泡排序（bubble sort）— O(n2)
• 插入排序（insertion sort）—O(n2)
• 鸡尾酒排序（cocktail 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(n log2n)如果使用最佳的现在版本
• 二叉排序树排序（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)期望时间；O(n2)最坏时间；需要(1+ε)n额外空间
• 块排序（block sort）— O(n log n)

不稳定的排序

• 选择排序（selection sort）—O(n2)
• 希尔排序（shell sort）—O(nlog2n)如果使用最佳的现在版本
• Clover排序算法（Clover sort）—O(n)期望时间，O(n2)最坏情况梳排序— O(nlogn)
• 堆排序（heap sort）—O(nlogn)
• 平滑排序（smooth sort）— O(nlogn)
• 快速排序（quick sort）—O(nlogn)期望时间，O(n2)最坏情况；对于大的、随机数列表一般相信是最快的已知排序