[数据结构与算法]链式存储结构的直接插入排序

链式存储结构的直接插入排序

LNode *CreateNode(int val) {
	LNode *node = (LNode*)malloc(sizeof(LNode));
	node->data = val;
	node->next = NULL;
	return node;
}

void InsertSort(LinkList *head) {
	LinkList *p = head->next, *s, *t, *q = head;
	while (p) {
		t = head, s = head->next;
		//找到插入的位置
		while (s && s->data < p->data) {//p插入s之前
			t = s;
			s = s->next;
		}
		q->next = p->next;
		p->next = t->next;
		t->next = p;
		
		q = p;
		p = p->next;
	}
	
}

int main() {

	//3, 5, 2, 10, 4, 8, 6, 7, 1
	LinkList *L = (LinkList*)malloc(sizeof(LinkList));
	LNode *p = L;
	p->next = CreateNode(3); p = p->next;
	p->next = CreateNode(5); p = p->next;
	p->next = CreateNode(2); p = p->next;
	p->next = CreateNode(10); p = p->next;
	p->next = CreateNode(4); p = p->next;
	p->next = CreateNode(8); p = p->next;
	p->next = CreateNode(6); p = p->next;
	p->next = CreateNode(7); p = p->next;
	p->next = CreateNode(1); p = p->next;

	InsertSort(L);

	LNode *q = L->next;
	while (q) {
		printf("%d ", q->data);
		q = q->next;
	}

	return 0;
}