排序算法总结

选择排序法

插入排序法

冒泡排序法

归并排序法

• 自顶向下
• 自底向上

快速排序法

• 单路快速排序法
• 双路快速排序法
• 三路快速排序法

堆排序法

希尔排序法

• 不同的步长序列

方法	时间复杂度	空间复杂度	特殊数据	其他	稳定性
选择排序法	O(n^2)	O(1)			不稳定
插入排序法	O(n^2)	O(1)	完全有序数组，时间O(n)		稳定的(依赖具体实现)
冒泡排序法	O(n^2)	O(1)	完全有序数组，时间O(n)		稳定的(依赖具体实现)
归并排序法	O(nlogn)	O(n)	完全有序数组，优化之后时间O(n)	O(nlogn)求数组中的逆序对个数	稳定的(merge过程中相同元素没机会跳到前面去)
快速排序法	O(nlogn) * (存在随机期望复杂度)	O(1)	含有相同元素数组，三路快排时间O(n)	O(n)求解selectK, topK	不稳定的(随机标定点直接打乱了顺序)
堆排序法	O(nlogn)	O(1) (优化heapify之后)		堆；优先队列 O(nlogk)解决selectK, topK问题	不稳定的
希尔排序法	O(nlogn)-O(n^2)	O(1)		分组的思想	不稳定(分组数据之间有间隔)

排序算法的稳定性

• 排序前相等的俩个元素，排序后相对位置不变。一个稳定的排序算法也有可能被实现成不稳定的。

• 如果元素只有一个域，稳定性没有意义。

  
  稳定性
  域