©2020-2024 ioDraw All rights reserved,
Privacy Policy
不是所有的排序算法都可以用单链表来实现，比如快速排序和堆排序，由于单链表不具有随机访问的特性，所以也受限制
本题中的简单选择排序，在单链表中实现的思路：每次遍历链表中的剩余部分，每一趟将剩余部分中最大结点插到表头，最后即可得一条由小到大的单链表，思路很简单，具体还得落实到代码上，你会了，不代表你的手也会了
#include<iostream> using namespace std; typedef struct Node{ int val; Node*next
; }Node,*ListNode; void build(ListNode &L)//尾插法 { L=(Node*)malloc(sizeof(Node));
int x; cin>>x; Node*p=L; while(x!=999){ Node*q=(Node*)malloc(sizeof(Node)); q->
next=nullptr; q->val=x; p->next=q; p=q; cin>>x; } } void visit(ListNode&L) {
ListNode p=L->next; while(p){ cout<<p->val<<" "; p=p->next; } cout<<endl; } void
selectsort(ListNode&L) { Node *h=L,*p,*q,*r,*s; L=NULL; while(h){ p=s=h;
//p为工作指针，q为其前驱，s指向最大结点，r为其前驱 q=r=nullptr; while(p){ //扫描原链表找最大结点s if(p->val>s->
val){ //找到更大的，记忆它和它的前驱 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;
} } int main() { ListNode L; build(L); visit(L); selectsort(L); visit(L); return
0; }