【链表】简单选择排序「建议收藏」

大家好，欢迎来到IT知识分享网。

题目描述：

编写一个算法，在基于单链表表示的待排序关键字序列上进行简单选择排序。

算法思想：

每趟在原始链表中摘下关键字最大的结点，把它插入到结果链表的最前端，由于在原始链表中摘下的关键字越来越小，在结果链表前端的关键字也越小。

因此，最后形成的结果链表中的结点将按关键字非递减的序列有序排列。

//假设单链表不带头结点
void selectSort(LinkList &L)
{
    LinkNode *h=L,*p,*q,*r,*s;
    L=NULL;
    while(h!=NULL)
    {
        //指针s和r记忆最大结点和其前驱
        p=s=h;
        //p为工作指针，q为其前驱
        q=r=NULL;
        while(p!=NULL)
        {
            if(p->data>s->data)
            {
                s=p;    //指向关键字最大结点
                r=q;    //指向关键字最大结点的前驱
            }
            q=p;        //向下遍历
            p=p->next;
        }
        if(s==h)        //最大结点在原链表前端
            h=h->next;
        else            //最大结点在原链表表内
            r->next=s->next;
        s->next=L;      //结点s插入到结果链表前端
        L=s;
    }
}

IT知识分享网