单链表 – 直接插入排序

直接插入排序就是：

• 先从待排序的元素中取出第一个元素。
• 取出的这个第一个元素当作有序区的第一个元素。
• 接着从待排序的元素中取出第二个元素。
• 然后将第二个元素插入到有序区中的合适位置，也就是，将第二个元素与第一个元素比较，谁小谁就排在有序区的前面。
• 接着，在待排序的元素中取第三个元素，然后再在有序区中比较，直至取遍所有待排序的元素。

例题

有一个带头节点的单链表 L (至少有一个数据节点)，设计一个算法使其元素递增有序排列。

分析

使用直接插入排序算法进行排序。

• 首先，我们需要构造出一个有序区，也就是构造一个存放有序区的列表。

// 使用原链表L构造了一个有序区，有序区中只有一个元素，
// 这个元素是链表L的开始节点(头节点之后的那个节点)
L->next->next = NULL;
复制

• 但是，发现将原链表L构造成有序区后发现，原链表的信息丢失了（开始节点之后的节点都没有了，变成了NULL），所以，在构造有序区之前需要保存下开始节点之后的信息。

// 使用指针p先保存下L中未排序元素（无序区中）的信息
p = L->next->next;
// 使用原链表L构造了一个有序区，有序区中只有一个元素，
// 这个元素是链表L的开始节点(头节点之后的那个节点)
L->next->next = NULL;
复制

• 接下来的任务就是遍历无序区中的元素，将它们一个一个的取出来。

// 使用指针p先保存下L中未排序元素（无序区中）的信息
p = L->next->next;
// 使用原链表L构造了一个有序区，有序区中只有一个元素，
// 这个元素是链表L的开始节点(头节点之后的那个节点)
L->next->next = NULL;
// 由于为了构造有序区，已经将待排序元素的第一个元素放在有序区中了，
// 所以从第二个元素开始遍历，也就是p = L->next->next。 
while(p != NULL){
	p = p->next; // 每循环一次p后移一位，直至p == NULL.
}
复制

• 每次从无序区中取一个元素后，接着应该将其和有序区中元素进行比较。

// 使用指针p先保存下L中未排序元素（无序区中）的信息
p = L->next->next;
// 使用原链表L构造了一个有序区，有序区中只有一个元素，
// 这个元素是链表L的开始节点(头节点之后的那个节点)
L->next->next = NULL;
// 由于为了构造有序区，已经将待排序元素的第一个元素放在有序区中了，
// 所以从第二个元素开始遍历，也就是p = L->next->next。 
while(p != NULL){
	// 为方便比较，用一个指针pre,指向有序区。
	pre = L;  
	// 遍历有序区中的所有元素，直至有序区末尾或者找到:
	// p所指的元素 大于 pre的next所指的元素为止，
	while(pre->next != NULL && pre->next->data < p->data)
		pre = pre->next;
	p = p->next; // 每循环一次p后移一位，直至p == NULL.
}
复制

• 经过比较过后，可以知道无序区中的第一个元素在有序区中的位置，接下来将其插入有序区中。

// 使用指针p先保存下L中未排序元素（无序区中）的信息
p = L->next->next;
// 使用原链表L构造了一个有序区，有序区中只有一个元素，
// 这个元素是链表L的开始节点(头节点之后的那个节点)
L->next->next = NULL;
// 由于为了构造有序区，已经将待排序元素的第一个元素放在有序区中了，
// 所以从第二个元素开始遍历，也就是p = L->next->next。 
while(p != NULL){
	// 每循环一次p后移一位，直至p == NULL.
	// 进行插入有序区的操作时会改变p->next的值所以需要选保存一下
	q = p->next; 
	// 为方便比较，用一个指针pre,指向有序区。
	pre = L;  
	// 遍历有序区中的所有元素，直至有序区末尾或者找到:
	// p所指的元素 大于 pre的next所指的元素为止，
	while(pre->next != NULL && pre->next->data < p->data)
		pre = pre->next;
	// 找到比p大的节点后，执行插入操作，因为插入操作需要用到
	// 被插入节点的前驱节点，所以在比较时，用了pre->next来和p比较
	p->next = pre->next;
	pre->next = p;
	// 用q把p的值恢复过来，使得循环继续指向无序区的下一个节点
	p = q;  
}
复制

完整的代码

void sort(LinkList * &L){
	LinkList *p,*pre,*q;
	p = L->next->next;		// 先保存下L的第二个元素，因为下一步要将L变成只有一个元素的有序表。  
	L->next->next = NULL;	// 将L变成只有一个元素的有序表
	// 从L的第二个元素开始遍历整个L直至表尾 
	while(p != NULL){
		q = p->next;
		pre = L;	// 先用pre来保存L。
		while(pre->next !=NULL && pre->next->data < p->data) // 遍历pre所指向的有序表L，直至找到比p大的节点 
			pre = pre->next; 
		p->next = pre->next;
		pre->next = p;
		p = q;	
	} 
}
复制