排序算法重点总结

前言

---

排序是算法入门的第一关，对排序算法性能的评价指标主要有：时间复杂度、空间复杂度和稳定性。

直观上讲，时间复杂度指实现算法的时间长短，空间复杂度指实现算法所需的内存大小。复杂度越高，实现所需时间越长，内存越大。

排序算法稳定性

---

什么是稳定性？

• 若排序比较的值相同时，排序后的相对顺序与排序前的相对顺序一致，则成为稳定排序
• 举例说明
  • 比如a数列中，a3/a7对应的数值相同，排序后，a3依然在a7的前面。

什么时候要考虑排序稳定性的问题？

• 如果数组只有单独键值，则一般无需考虑排序稳定性问题
• 如果数组是个结构体，排序依据是其中一种键值，但其他值又不同时，希望键值相同时，不改变原始相对顺序。则务必要考虑排序稳定性。
• 举例说明
  • 比如结构体数组a[20]，其中i个a[i]里面存有：age,class, grade等值，已经按照grade分数总体降序排好
  • 现在要求再按照age年龄降序排列后，希望年龄相同时，依然按照原来的grade降序排列，不改变原来的顺序
  • 此时则需要考虑稳定性问题，以保证比较键值相同时，原始相对顺序不变

排序算法特点

---

那么哪些排序算法是稳定的呢？其算法实现的时间、空间复杂度又如何？

排序算法稳定性：

• 仅以下排序算法是稳定的
  • 选择（冒泡）、插入和归并、基数
• 其余均为不稳定：
  • 快排、希尔、简单选择排序、堆排and so on

8种排序算法特点：

其中，归并、快排、冒泡使用的较多。

归并算法特点：

• 优势
  • 满足排序稳定
  • 最好最坏时间复杂度O(NlogN)
• 劣势
  • 需增加O(N)的空间
• 原理：
  • 类似树的后序遍历，先到底（无法再拆分为止），然后操作合并
  • 分治思想

相关资料

---

1. 用C语言实现快速排序算法，link
2. 8个算法复杂度及稳定性分析，link
3. 菜鸟教程：排序算法总结及源代码实现，link