链表排序 1.怎么对单向链表进行快速排序

一、1.怎么对单向链表进行快速排序

将单向链表拓展为双向链表，然后按照快排的方式排序，这需要O(n)的空间，比数组O(logn)大不少，但能保证O(nlogn)完成

二、以单链表为存储结构实现直接插入排序的算法

排序，是数据结构中重要的一部分。今天做单链表的直接插入排序和简单选择排序。首先，先解决单链表的存储结构和创建单链表。单链表的结构：typedefstructlist{ intdata; structlist*next;}list,*linklist;单链表的创建（使用了引用，应为在创建链表的时候，头节点申请空间，头结点地址有变化，可以改为指针的指针）：voidcreate(linklist&L,intn){ inti; linklistp; L=(linklist)malloc(sizeof(list)); L->next=NULL; for(i=0;i<n;i++) { p=(linklist)malloc(sizeof(list)); scanf("%d",&p->data); p->next=L->next; L->next=p; }}单链表的打印：voidshow(linklistL){ linklistp; p=L->next; while(p) { printf("%d\t",p->data); p=p->next; }}--------------------------------俄是分界线------------------------------单链表的基本操作就已经完事了，接下来先看看直接插入排序。直接插入排序是一个稳定的排序，所谓稳定的排序就是假如待排数中有两个相同的数值，在排序后其先后关系保持不变。其时间复杂度平均为O（），空间复杂度为O（1）。直接插入法的思想是：默认首个数据是排序好的，在待排序表中拿出首个数据与排序表进行比较，改变指针的指向进而进行排序，直到全部有序（由于是单链表，所以不能从后往前比较，只能从前往后比较，这点与存储结构是数组的直接插入法不一样）具体排序简析图voidinsertsort(linklistL){ linklistp,q,pre; p=L->next->next; L->next->next=NULL; while(p) { q=p->next; pre=L; while(pre->next!=NULL&&pre->next->data<p->data) pre=pre->next; p->next=pre->next; pre->next=p; p=q; }}----------------------------------俄也是分界线--------------------------------看完直接插入排序，那简单选择排序就更简单了。简单选择排序也是稳定的排序，其时间复杂度和空间复杂度和直接插入排序一样。简单选择排序思想：从头到尾进行扫描，找到最小的放在第一个位置，在从第二个位置进行第二次扫描，找到最小的，放在第二个位置，依次扫描，直到全部有序。简单选择排序简析图简单选择排序代码：linklistmin(linklistp){ intda; linklisttemp=p; da=p->data; p=p->next; while(p) { if(p->data<da) { temp=p; da=p->data; } p=p->next; } returntemp;}voidselectsort(linklistL){ linklistp,q; q=p=L->next; while(q) { p=min(p); inttemp=p->data; p->data=q->data; q->data=temp; q=q->next; p=q; }}----------------------------俄还是分界线-----------------------实验结果：默认为输入五个数，显示两种排序的结果。实验结果-----------------------------俄真的是分界线---------------------------当然了，这两种排序算法时间复杂度还是挺高的，还有更快的排序算法，比如著名的快排，堆排，基排（多关键字排序），在今后的学习中会更新。至于存储结构是数组的，这两个排序算法写着就更简单了，本次就不写了。快考试了，哈哈，紧张紧张。

如果你还想了解更多这方面的信息，记得收藏关注本站。