该文章为清华大学数据结构与算法设计MOOC课程读书笔记.
1. 节点ADT接口
节点ADT接口
2. 列表ADT接口
列表ADT接口
3. 无序列表
思路：有header和trailer两个哨兵(sentinel)节点
- find(e)
- insertAfter(p, e) & insertBefore(p, e)
- copyNode(p, n)
- remove(e)
- clear()
- deduplicate()
4. 有序列表
- uniquify() --> 双指针O(N)
- search(e) ---> 平均O(N),并不能比无序列表好
5. 排序
5.1 选择排序 Selection Sort
思路
其实就是稍微优化版的bubble sort。保证后半部分sorted，前半部分unsorted。但是，每次扫描中找最大的，在最后时刻才换到最后的位置。这样可以减少交换的次数。-
实现
选择排序实现 效率
最好，最差都是O(N^2)
虽然我们知道理论上是ON^2)，但是细节之处值得推敲！
比如，虽然理论上对于insert或者remove一个节点都只需要O(N)，但是实际上节点的这种新建或者删除的动态空间分配方式(dynamic memory allocation)是相当耗时的！应该尽可能地避免这些操作，那怎么办呢？比如我们可以尝试只是修改指针，或者甚至只是交换两个节点的值！😏
- 稳定性
取决于如何选max，如果只要cur >= max, cur = max的话，那么就能保证每次都是找到最大的最后一个，因此是稳定的。
5.2 插入排序 Insertion Sort
-
思路
前部分有序，后部分无序。不断将带插入的元素插到有序部分中的对应位置去。
插入排序 -
实现
插入排序实现 效率
最好O(N)，只需要走一遍，每个位置只需要比较1次，不需要交换。
最坏O(N^2)
平均O(N^2)
- 逆序对Inversion
插入排序的算法复杂度实际上就是O(I + n)
其中I是逆序对的数量，n是元素插入的耗时（每个元素插入O(1)，共n个元素）。insersion sort的耗时相当于不断地去修复这种无序性。
另一个方面也说明了，该算法的复杂度实际上取决于input的属性，属于input sensitive的算法。
因此，最好情况: I = 0, 无逆序对
最坏情况：I = N^2，因为任何两个元素都构成逆序对
逆序对分析
