[数据结构与算法]数据结构学习（列表：五（有序列表的排序算法））

有序列表

选择排序

选择排序算法将有序列表的分为无序前缀和有序后缀两部分，此外，还要求不大于后缀，如此，只需要从前缀中挑出最大者，并作为最小元素转入后缀中，即可使有序部分的范围不断扩张。这个算法的不变性是：在任何时刻，后缀（r，n）已经有序，且不小于前缀S[0，r]。
算法初始时刻，后缀为空，不变性自然满足。于是在前缀中找出最大者，并作为首元素插入后缀，使得后缀的范围扩大，并继续保持有序。如此，该后缀的范围不断扩大，直至最终覆盖整个序列，亦即整体有序。

//对起始于位置p的n个元素进行排序
template <typename T> void List<T>::selectionSort(Posi(T) p, int n)
{
	Posi(T) head = p -> pred;
	Posi(T) tail = p;
	for(int i = 0; i < n; i++) tail = tail -> succ;//待排序区间为（head, tail）
	while(1 < n)   //在至少还有两个节点之前，在待排序区间内
	{
		Posi(T) max = selectMax(head -> succ, n);//找出最大者
		insertBefore(tail, remove(max)); //将其移至无需区间末尾（作为有序区间新的首元素）
		tail = tail -> pred; n--;
	}
}

//关于selectMax函数
template <typename T> Posi(T) List<T>::selectMax(Posi(T) p, int n)
{
	Posi(T) max = p;//最大者暂定为首节点p
	for(Posi(T) cur = p; 1 < n, n--)//从首节点出发，将后续节点逐一与max比较
		if(!lt((cur = cur -> succ) -> data, max -> data))//若当前元素不小于max，则
			max = curr; //更新最大元素位置记录
	return max; //返回最大节点位置
} 

复杂度：可以观察到，有序列表选择排序算法无论是什么情况，它的复杂度都是O（n^2）

插入排序

插入排序在我生活中经常用到，比如我们在打扑克时，每次都抽取一张牌，然后将这张牌按照顺序插入到手里已排好序的牌中，抽取完最后一张牌后，手里的牌已经是全部排好序的了。
我们可以将一个整个列表视作并切分成两部分：有序的前缀、无序的后缀。通过迭代，反复将后缀的首元素转移至前缀中，由此，可看出该算法的不变性：==在任何时刻，相对于当前节点e=S[r], 前缀S[0, r)总是有序。==算法开始时前缀为空，不变性自然满足。
可能会觉得插入排序与选择排序相差不大，但是这两者有着本质区别：选择排序中，后缀是有序的，无需前缀中的任何一个元素都是不大于后缀的；而在插入排序中，相对于有序前缀，无需后缀中的任何一个元素对于前缀中的元素可能大于小于或者是等于的。
所以插入排序的任务就是每次将后缀中的首元素依据顺序插入到相应的位置：

template <typename T> void List<T>::insertSort(Posi(T) p, int n)
{
	for(int r = 0; r < n; r++)  //逐一遍历各节点
	{
		insertAfter(search(p -> data, r, p), p -> data) //在适当位置进行插入
		p = p -> succ;  //转向下一节点
		remove(p -> pred);
	}
}

复杂度：最好O（n）， 最坏O（n^2）

这里我们说一下序列中的逆序对，逆序对一定是由两个元素组成的，可可能相邻也可能不相邻。但是后者一定小于前者。为了方便统计，我们可以将每个逆序对计入后者元素的帐上，这样考察一个元素中有多少逆序对，只需考察在这个元素之前有多少各元素比它大即可。在插入排序算法中，时间复杂度主要花费在每一轮迭代中search算法里，在search算法里要进行多次比较。所以我们可以知道比较的次数s与逆序对的数量T的关系为：s = T+n，n为问题的规模，也就是列表元素个数。所以，插入排序算法的比较次数除了由问题规模决定之外，也与逆序对个数的有关系。当列表为最好情况：即整体都是有序的，那么逆序对个数为0，比较次数就为n，所以时间复杂度为O（n）；当为最坏情况：逆序对个数为：n（n-1）/ 2, 所以时间复杂度为O（n^2）。
而逆序对的个数在列表输入时就已经决定。像这种时间复杂度由输入影响的算法被称之为输入敏感型算法。