PS-03 List

1. 从向量到列表

循位置访问

列表中各元素的物理位置不决定于逻辑位置,利用节点之间相互引用，找到特定的节点

动态操作复杂度为 $O(1)$

ADT接口

2. 无序列表

插入

进行一个指针的换向就OK了

删除

仍然是进行指针的换向

查找

列表二分查找的成本太高，因此只采取顺序查找

去重

与无序向量的去重方法相同

遍历

顺序遍历

3. 有序向量

唯一化

感觉和有序向量的勤奋算法是一样的思路，但是列表的动态删除是 $O(1)$的时间，所以复杂度也只是 $O(n)$

查找

仍然是顺序查找，仍然能满足向量的找到不大于e的最大的节点，从而保证插入的有序和稳定性

选择排序

如果用冒泡排序，每次扫描需要 $O(n)$次比较， $O(n)$次交换，而列表的交换又比较慢且没有必要，所以用选择排序，在每次扫描找到最大者，交换一次即可。选择排序相比与起泡排序，优化的是常数项

性能分析

复杂度仍为 $\Theta (n^{2})$，但时间都花在了比较上

4. 循环节

一个元素占了另一个元素的位置，这个元素又占了另另一个元素的位置，这样循环下去，最终回到起点（类似三角债），这样就构成了一个循环节

选择排序每交换一次，最大元素就跳出了原来的循环节，独立成一个新的循环节

当循环节达到 $n$个时，排序就完成了

5. 插入排序

一个在线的算法

首先有一个有序序列（长度可能为0），对于每一个新来的元素，找到合适的位置插入即可

从期望的意义上来讲，时间复杂度为 $O(n^{2})$

• 略证

  插入 $S[r]$所花时间为 $1+\sum^{r}k/(r+1)=1+r/2$

  插入 $n$个所花期望总时间为 $\sum^{n-1}(1+r/2)=O(n^{2})$

6. 归并排序

复杂度依然为 $O(nlogn)$

7. 逆序对

如果 $0≤i<j<n,A[i]>A[j]$，则称其为一逆序对

逆序对总数 $≤O(n^{2})$

Bubblesort

起泡排序的每次交换都会使整体逆序对的个数减1，因此交换的总次数为逆序对总数

Insertionsort

运行时间为逆序对个数+n

统计逆序对个数

借助归并排序，复杂度为 $O(nlogn)$为什么？？？

8. 游标实现

用双数组来模拟链表，但是是单向的列表，也可以用三数组来模拟列表