基本思想

插入排序的基本思想是：维护一个有序序列，初始时有序序列只有一个元素，每次将一个新的元素插入到有序序列中，将有序序列的长度增加 1，直到全部元素都加入到有序序列中。

对上述链表：

p：工作指针，用于遍历无序表。

r：p的后继，用于防止断链后丢失。

q：用于遍历有序表，寻找插入的位置。

操作流程

① 将链表的首元节点（p指向处）与其后继（r指向处）断开（p->next=NULL）

​ 分解处前部为有序表，后部为无序表。

② p进入无序表（p=r）

③ 遍历无序表，逐个取出无序表中的元素，找到其在有序表中的位置

代码实现

//升序排序
struct node *insert_sort(struct node *head)
{
    p=head->next;
    r=p->next;
    p->next=NULL;
    p=r;

    while(p!=NULL)
    {
        r=p->next;
        q=head;
        while(q->next!=NULL&&q->next->data<p->data)
        {
            q=q->next;
        }
        p->next=q->next;
        q->next=p;
        p=r;
    }

    return head;
}