【数据结构与算法】单链表的排序算法(选择，冒泡，递归）

您所在的位置：网站首页 › 排序算法的选择方法 › 【数据结构与算法】单链表的排序算法(选择，冒泡，递归）

【数据结构与算法】单链表的排序算法(选择，冒泡，递归）

2024-07-15 01:04| 来源: 网络整理| 查看: 265

目录选择排序冒泡排序快速排序合并两条链表并排序选择排序

链表的选择排序思想与数组的排序类似，但是链表需要先找到里面最小或者最大的值，然后将这个值用改链语句进行操作

我们先看这个改链语句的操作（min是笔者打错了应该是max，但是图已经画好了就没有改）

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7tlNdmSk-1669548013594)(C:\Users\孙文宇\OneDrive\图片\11-27\Snipaste_2022-11-27_16-17-34.png)]$ 移动q这个指针找到最大的min，然后利用i保存q的前一个节点这样就能找到min_on.

接下来进行改链语句的操作

min_on->next = min->next; // 1

min->next = tail->next; // 2

tail->next = min; //3

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wdT8h1Ze-1669548013595)(C:\Users\孙文宇\OneDrive\图片\11-27\Snipaste_2022-11-27_16-22-19.png)]$ 接下来将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 三个数由大到小排序

数字245nullp1tail

初始时令tail == null；让p从1位置开始移动

结束条件是p ！= tail，

这样第一次时：就能保证1交换两次，接下来将tail向前移动，让tail = null的前一个位置；

此时我们将2下沉到底部；数据变为：4，5，2

数字452nullp1tail

p继续从1 位置开始移动

第二次时就能保证4交换1次；数据就变成了5，4，2完成排序。

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gKadKCyu-1669548013595)(C:\Users\孙文宇\OneDrive\图片\11-27\Snipaste_2022-11-27_17-41-04.png)]$ 接下来我们看如何进行改链操作

p->next = q->next; //1

q->next = q->next->next; //2

p->next->next = q; //3

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HAaWqGy5-1669548013595)(C:\Users\孙文宇\OneDrive\图片\11-27\Snipaste_2022-11-27_17-50-46.png)]$ 接下来移动q的位置使得p，q始终相邻.

q = p->next;

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BYcR4azK-1669548013595)(C:\Users\孙文宇\OneDrive\图片\11-27\Snipaste_2022-11-27_17-53-02.png)]$ 代码如下：

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；

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FCrdDlaV-1669548013596)(C:\Users\孙文宇\OneDrive\图片\11-27\Snipaste_2022-11-27_18-33-43.png)]$ 接下来进行改链操作，假定为由小到大排序

i->next = p->next; //1 p->next = head->next; //2 head->next = p; //3

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JaYUutEk-1669548013596)(C:\Users\孙文宇\OneDrive\图片\11-27\Snipaste_2022-11-27_18-39-47.png)]$ 此时改链完成我们得到

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nDs0pDaO-1669548013596)(C:\Users\孙文宇\OneDrive\图片\11-27\Snipaste_2022-11-27_18-42-12.png)]$ 那么如果后面的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 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

我们首先将两个链表连接

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链表 }

然后我们就可以将链表进行排序了，完整的代码如下

#include #include 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; } }

【本文地址】

【数据结构与算法】单链表的排序算法(选择，冒泡，递归）

【数据结构与算法】单链表的排序算法(选择，冒泡，递归）

今日新闻

推荐新闻