1.比较排序：快速排序、堆排序、归并排序、插入排序等。基于比较的排序时间复杂度下限为O(n log n)
2 线性时间排序：计数排序、基数排序、桶排序等
3 稳定排序
--快速排序
在主元元素a[r]和a[i+1]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为3 3 5 4 3 8 9 10 1，主元为1，第一轮划分后为1 3 3 5 4 3 8 9 10 3，把最开始的3换到了最后，元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[i+1] 交换的时刻。所以快速排序是不稳定的。
---插入排序
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
--堆排序
比如：3 27 36 27，
如果堆顶3先输出，则，第三层的27（最后一个27）跑到堆顶，然后堆稳定，继续输出堆顶，是刚才那个27，这样说明后面的27先于第二个位置的27输出，所以堆排序是不稳定的。
--规并排序
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换），然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。
--基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。
--计数排序（稳定的）
4 原地排序
| 排序算法 | 平均时间 | 最差时间 | 稳定度 | 额外空间 | 备注说明 |
| 冒泡排序 | O(n2) | O(n2) | 稳定 | O(1) | n小时较好 |
| 选择排序 | O(n2) | O(n2) | 不稳定 | O(1) | n小时较好 |
| 插入排序 | O(n2) | O(n2) | 稳定 | O(1) | n小时较好 |
| 归并排序 | O(nlogn) | O(nlogn) | 稳定 | O(n) | n大时较好 |
| 快速排序 | O(nlogn) | O(n2) | 不稳定 | O(logn) | n大时较好 |
| 堆排序 | O(nlogn) | O(nlogn) | 不稳定 | O(1) | n大时较好 |
| 计数排序 | O(n) | O(n) | 稳定 | O(n+k) | 输入序列限制 |
| 基数排序 | O(n) | O(n) | 稳定 | O(n+k) | 输入序列限制 |
| 桶排序 | O(n) | O(n) | 稳定 | O(n) | 输入序列限制 |