（C语言）链表排序 --- 插入排序
转自https://blog.csdn.net/trb331617/article/details/79459643
/*
* FILE: sort_link.c
* DATE: 20180306
* ==============
* DESCRIPTION: 链表插入排序
*/
#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node *next;
};
void display(struct node *);
int main(int argc, char *argv[])
{
struct node a; // 准备一个空的头节点，可简化代码
struct node *p;
int i, len = 10;
p = &a;
srand(time(NULL)); // 随机数种子
for(i=0; i<len; i++)
{
p->next = (struct node *)malloc(sizeof(struct node));
p = p->next;
p->data = rand() % 100; // 0-100间的随机数
}
p->next = NULL;
display((&a)->next);
struct node b = {0, NULL};
struct node *q, *temp;
// 待排序链表中每次取出一个节点，
// 插入进已排好序链表的合适位置
p = (&a)->next;
while(p != NULL)
{
temp = p->next; // 临时保存下一个节点
q = &b;
while(q->next != NULL) // 遍历已排好序的链表，寻找合适的位置插入
{
if(p->data < q->next->data)
break;
q = q->next;
}
// 已找到合适位置插入
p->next = q->next;
q->next = p;
p = temp;
}
display((&b)->next);
//display((&a)->next);
return 0;
}
void display(struct node *head)
{
struct node *p = head;
while(p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
