考研算法题练习2022.11.16

1. 实现对链表的插入排序

//插入排序思想：不断的从待排序的序列中去节点插入到已经有序的链表中合适的位置，并保证不断链 
//其中，head是已经有序的链表表头，rear是已经有序的链表表尾
//q是待排序序列的第一个节点 
void InsertSort(LinkList &l){
	LNode *head=l,*rear=head->next,*q=rear->next;
	while(q!=NULL){
		if(q->data<rear->data){
			rear->next = q->next;
			while(head->next->data<q->data)head = head->next;
			q->next = head->next;
			head->next = q;
			head = l;
			q = rear->next;
		}else {
			rear = rear->next;
			q = q->next;
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20