排序算法重点总结
排序算法重点总结
- 前言
- 排序算法稳定性
- 排序算法特点
- 相关资料
前言
排序是算法入门的第一关，对排序算法性能的评价指标主要有：时间复杂度、空间复杂度和稳定性。
直观上讲，时间复杂度指实现算法的时间长短，空间复杂度指实现算法所需的内存大小。复杂度越高，实现所需时间越长，内存越大。
排序算法稳定性
什么是稳定性？
- 若排序比较的值相同时，排序后的相对顺序与排序前的相对顺序一致，则成为稳定排序
- 举例说明
- 比如a数列中，a3/a7对应的数值相同，排序后，a3依然在a7的前面。
什么时候要考虑排序稳定性的问题？
- 如果数组只有单独键值，则一般无需考虑排序稳定性问题
- 如果数组是个结构体，排序依据是其中一种键值，但其他值又不同时，希望键值相同时，不改变原始相对顺序。则务必要考虑排序稳定性。
- 举例说明
- 比如结构体数组
a[20]，其中i个a[i]里面存有：age,class, grade等值，已经按照grade分数总体降序排好 - 现在要求再按照age年龄降序排列后，希望年龄相同时，依然按照原来的grade降序排列，不改变原来的顺序
- 此时则需要考虑稳定性问题，以保证比较键值相同时，原始相对顺序不变
- 比如结构体数组
排序算法特点
那么哪些排序算法是稳定的呢？其算法实现的时间、空间复杂度又如何？
排序算法稳定性：
- 仅以下排序算法是稳定的
- 选择（冒泡）、插入和归并、基数
- 其余均为不稳定：
- 快排、希尔、简单选择排序、堆排and so on
8种排序算法特点：
其中，归并、快排、冒泡使用的较多。
归并算法特点：
- 优势
- 满足排序稳定
- 最好最坏时间复杂度
O(NlogN)
- 劣势
- 需增加
O(N)的空间
- 需增加
- 原理：
- 类似树的后序遍历，先到底（无法再拆分为止），然后操作合并
- 分治思想
相关资料
- 用C语言实现快速排序算法，link
- 8个算法复杂度及稳定性分析，link
- 菜鸟教程：排序算法总结及源代码实现，link