DESCRIPTION

---

Reference

1. 《数据结构与算法－Python语言描述》裘宗燕
2. Python Data Structures - C1 Search
3. Python Data Structures - C2 Sort
4. Python Data Structures - C4 Trees
5. 这些数据结构与算法的Java实现
6. 狗皮膏药的主页，有很多讲原理的东西~~博主也是我的好朋友，推广一下^_^

Sort Summary

sorting_summary.py只列了直接插入、直接选择、冒泡、归并和快速这5种排序方法。

1. 稳定性 含义：若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；反之则称该算法是不稳定的。 好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，可以避免多余的比较。
2. 时间复杂度的说明 原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至$ O(n) $；但此时快速排序将蜕化为冒泡排序，时间复杂度提高为$O(n^2)$。 原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。
3. 如何选择合适的排序方法 平均时间复杂度低的算法并不一定就是最优的，一般而言，需要考虑的因素有以下四点：

1. 待排序的记录数目n的大小；
2. 记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小；
3. 关键字的结构及其分布情况；
4. 对排序稳定性的要求。 因此可借鉴：
   1. 一般不使用或不直接使用传统的冒泡排序；
   2. 序列较大，内存空间允许且要求稳定性，考虑归并排序；
   3. 归并与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高；
   4. 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，它的平均时间最短。