Question

C++链表排序问题（一个链表有多个元素）

struct Student {
long number;
string name;
string gender;
string major;
Student *next;
};//链表元素
Student *create();//创建链表函数
Student *head;//定义头指针
其他过多的我就不写了，我想知道链表如何按照number元素进行排序

Answer 1

用选择法排序，和数组的排序一样

追问

可以具体一点吗

追答

void sort(Student *h)
{
  Student *p,*q,*t;
  p=h; 
  while(p!=NULL)
  {
     t=p;
     q=p->next;
     while(q!=NULL)
     {
       if(q->number>t->number)
         t=q;
       q=q->next;
      }
      Student *pp=p;
       p=t;
       t=pp;     
     p=p->next;    
   }    
}

Answer 2

链表排序，真正写起来很啰嗦，花时间在链表遍历，节点交换上，算法还是可以用冒泡法，选择法。如果双向链表，在创建的时候用插入法排序也很方便。
还有一种项目常见的做法：临时创建一个指针数组，每个元素依次指向链表，然后直接用C库函数 qsort排序，这样链表不用变，但数组中指针指向链表节点就是正确的排序了。