链表的插入排序过程(从头插入)

void InsertSort(Node *sq)//sq是一个链表的指针(含头结点)

{
    Node*p=sq->next, *pre,*q;
    sq->next=NULL;//这两行的初始化问题,就是为添加第一个结点准备.特别请注意要将头的next指为空.

    while(p!=NULL)//p是指向待排序的结点,这个条件就是没有要排序的结点了.

    {
        if(sq->next==NULL)
        {
            sq->next=p;
            p=p->next;
            sq->next->next=NULL;//完成第一个结点的排序,排序后又将最后一个已排好的结点的next置为空

        }
        else
        {
            pre=sq;q=sq->next;//总是从头开始,去找并移动.

            while(q!=NULL && q->expn<p->expn)//q==NULL,就是说已到了前面排好序的最后位置.也正是sq->next->next=NULL的承接.

            {//只要移动到一个比p要大的元素位置.也停下来.此时pre指我们就应该插入的元素的位置.

                pre=q;q=q->next;
            }
            q=p->next;//此句是保存下一个待排序的结点位置.由于p要参与下面的运算,这个值要保存.

            p->next=pre->next;//完成在pre之后的对p指向位置的连接.

            pre->next=p;
            p=q;//最后又要将p指回它的下一个待排序的位置.

        }
    }
}