目录
- 选择排序
- 冒泡排序
- 快速排序
- 合并两条链表并排序
选择排序
链表的选择排序思想与数组的排序类似，但是链表需要先找到里面最小或者最大的值，然后将这个值用改链语句进行操作
我们先看这个改链语句的操作（min是笔者打错了应该是max，但是图已经画好了就没有改）
移动q这个指针找到最大的min，然后利用i保存q的前一个节点这样就能找到min_on.
接下来进行改链语句的操作
min_on->next = min->next; // 1
min->next = tail->next; // 2
tail->next = min; //3
接下来将tail前移一位重复操作。
void insert(li *head) //传进来一个有头节点的链表
{
li* tail,*i,*min,*q,*min_on;
/*注意条件是 tail&&tail->next 因为如果tail->next == null
会使程序进入里面的for循环出现问题*/
for(tail = head; tail&&tail->next; tail=tail->next)
{
min = tail->next;
for(q = tail->next,i = tail; q; i=q,q=q->next) //i是p的上一个节点
{
if(q->digit > min->digit) //寻找最大的数
{
min = q;
min_on = i; //保存min的上一个节点
}
}
if(tail->next != min) //如果找到比tail->next更小的 min那么就进行插入
{
min_on->next = min->next;
min->next = tail->next;
tail->next = min;
}
}
}
冒泡排序
冒泡排序最重要的一步就是将元素下沉，然后重新判断循环次数
在这里我们首先引入一个tail的变量
#例如2，4， 5，null 三个数由大到小排序
| 数字 | 2 | 4 | 5 | null |
|---|---|---|---|---|
| p | 1 | tail |
初始时令tail == null；让p从1位置开始移动
结束条件是p ！= tail，
这样第一次时：就能保证1交换两次，接下来将tail向前移动，让tail = null的前一个位置；
此时我们将2下沉到底部；数据变为：4，5，2
| 数字 | 4 | 5 | 2 | null |
|---|---|---|---|---|
| p | 1 | tail |
p继续从1 位置开始移动
第二次时就能保证4交换1次；数据就变成了5，4，2完成排序。
接下来我们看如何进行改链操作
p->next = q->next; //1
q->next = q->next->next; //2
p->next->next = q; //3
接下来移动q的位置使得p，q始终相邻.
q = p->next;
代码如下：
void bubbling(li *head) //传进来一个有头节点的链表
{
li *tail,*p,*q;
tail = NULL;
/*假定如果三个数排序，第二个数确定了那么
第一个也就确定了，不需要对第一个数排序*/
while((head->next->next) != tail)
{
p = head;
q = head->next;
/*冒泡排序的本质将所找到的数都下沉，所以内层循环比外层小一个节点*/
while((q->next) != tail)
{
if((q->digit) > (q->next->digit)) //不停判断两个相邻的数并且交换顺序
{
p->next = q->next;
q->next = q->next->next;
p->next->next = q;
q = p->next; //始终保存p，q是相邻的位置
}
q = q->next;
p = p->next;
}
/*最重要的一步，将tail不停向前移动*/
tail = q;
}
}
快速排序
数组快速排序的思想和链表的一样，主要问题就是存在改链的操作。
首先我们还是做一个类似二分法的递归操作，叫做"分", 接下来分别给两边节点排序
void quick_sort(node *head, node *tail) //传进来一个有头节点的链表，初始时tail为NULL
{
//头结点是空的或者表是空的或者表只有一个节点时候不用排
//tail是链表的结束点，一开始等于NULL,后面等于privot
if(!head || head->next == tail || head->next->next == tail)
{
return ;
}
//baisc前的节点都比basic小，baisc后的节点都比baisc大
node *privot = partition(head, tail);
/*因为在"治"的操作中privot会变成下一个节点，
所以此时和数组时不一样，不需要类似privot-1/+1的操作*/
quick_sort(head, privot); //把head->next到privot前一个进行递归排序
quick_sort(privot, tail); //从privot->next到tail前一个进行递归排序
}
接下来我们进行排序，首先选取一个基准点，如何将比基准点大/小的值放左边，比基准点小/大的放右边。
例如2，1，4，null的改链操作
先得到一个基准点 privot = head->next
privot->digit = 2；
接下来进行改链操作，假定为由小到大排序
i->next = p->next; //1 p->next = head->next; //2 head->next = p; //3
此时改链完成我们得到
那么如果后面的4还需要排序的话我们可以将 p = i->next 然后重复以上步骤进行排序。
"治"的代码如下：
node *partition(node *head, node *tail) //结构体指针类型函数，需要一个结构体指针的返回值
{
//头结点是空的或者表是空的或者表只有一个节点时候不用排
//已经在调用函数前判断好了，进来的链表都是至少有两个元素的
node *p, *i, *privot;
privot = head->next; //privot是基准点
//从privot后面开始遍历，找到比privot小的就插入到head后面，直到tail结束，i是p的前驱节点
//这里head可以理解为本次待划分的链表的头结点，tail是链表的最后一个节点的下一个可以理解为NULL
for(i = privot, p = privot->next; p && p != tail; p = i->next)
{
if(privot->digit < p->digit) //用头插入法把所有比privot小插入到head后面
{
i->next = p->next;
p->next = head->next;
head->next = p;
}
else //没有找到比privot小的就一直后移，i与p同时后移
{
i = i->next;
}
}
return privot;
}
合并两条链表并排序
接下来我们练习一道例题，将两个链表合成为一个链表并使它有序
输出：
1 3 5 5 6
4 2 5 1 9
输出：
1 1 2 3 4 5 5 5 6 9
我们首先将两个链表连接文章来源：https://www.toymoban.com/news/detail-759821.html
void sum(mlist *a,mlist *b) //传入两个带有头节点的链表
{
mlist *p;
p = a;
while(p->next)
{
p = p->next;
}
//释放掉b链表的表头
mlist *t = b;
b = b->next;
free(t);
p->next = b; //连接a,b链表
}
然后我们就可以将链表进行排序了，完整的代码如下文章来源地址https://www.toymoban.com/news/detail-759821.html
#include <stdio.h>
#include <stdlib.h>
typedef struct _lis{
int digit;
struct _lis *next;
}mlist;
typedef struct _ls{
mlist *head;
}helist;
void make(mlist *meter); //制作链表
void sum(mlist *a,mlist *b); //链表合成
void output(mlist *meter); //输出链表
void bubbling(mlist *head); //冒泡排序
int main()
{
helist a,b;
a.head = (mlist*)malloc(sizeof(mlist));
a.head->next = NULL;
b.head = (mlist*)malloc(sizeof(mlist));
b.head->next = NULL;
printf("请输入a链表\n");
make(a.head); //制作链表
printf("请输入b链表\n");
make(b.head);
sum(a.head,b.head); //链表连接
bubbling(a.head); //链表排序
output(a.head); //输出链表
}
void make(mlist *meter) //制作
{
int number;
mlist *t;
t = meter;
while(scanf("%d",&number) != EOF) //尾插法制作一个链表
{
mlist *p = (mlist*)malloc(sizeof(mlist));
p->digit = number;
p->next = NULL;
t->next = p;
t = p;
}
}
void output(mlist *meter) //输出
{
for(mlist *i = meter->next; i; i=i->next)
{
printf("%d\t",i->digit); //输出节点的值
}
printf("\n");
}
void sum(mlist *a,mlist *b) //连接
{
mlist *p;
p = a;
while(p->next)
{
p = p->next;
}
//释放掉b链表的表头
mlist *t = b;
b = b->next;
free(t);
p->next = b; //连接a,b链表
}
void bubbling(mlist *head) //排序，传进来一个有头节点的链表
{
mlist *tail,*p,*q;
tail = NULL;
/*假定如果三个数排序，第二个数确定了那么
第一个也就确定了，不需要对第一个数排序*/
while((head->next->next) != tail)
{
p = head;
q = head->next;
/*冒泡排序的本质将所找到的数都下沉，所以内层循环比外层小一个节点*/
while((q->next) != tail)
{
if((q->digit) > (q->next->digit)) //不停判断两个相邻的数并且交换顺序
{
p->next = q->next;
q->next = q->next->next;
p->next->next = q;
q = p->next; //始终保存p，q是相邻的位置
}
q = q->next;
p = p->next;
}
/*最重要的一步，将tail不停向前移动*/
tail = q;
}
}
到了这里，关于【数据结构与算法】单链表的排序算法(选择，冒泡，递归）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
