数据结构和算法-交换排序中的冒泡排序（过程 代码实现 算法效率 稳定性 适用链表？）

发布时间：2024年01月06日

文章目录

总览

在这里插入图片描述

冒泡排序

冒泡？

自然界的冒泡
在这里插入图片描述

啥是冒泡排序

在这里插入图片描述

冒泡排序过程

此时序列要求递增的
首先比较27和49，发现符号递增序列，小的在左边
在这里插入图片描述
再比较13和27，此时小的依然在左边，符号
在这里插入图片描述
再比较76和13，此时小的在右边，交换
在这里插入图片描述
此时13已经交换到76的位置了，再比较97和13，小的在右边，交换
在这里插入图片描述
此时13交换到97的位置了，再比较65和13，小的在右边，交换
在这里插入图片描述
此时13交换到65的位置了，比较38和13，小的在右边，交换
在这里插入图片描述
此时13交换到38的位置了，比较49和13，小的在右边，交换
在这里插入图片描述
第一趟冒泡排序结果
在这里插入图片描述
开始第二趟，和之前步骤一样
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
此时不需要和之前冒泡出来的元素对比
在这里插入图片描述
第二趟结果
在这里插入图片描述
第三趟即后面都类似
每趟都会从剩下的没确定位置的找到最小的排到之前已确定位置的元素后面
注意第四趟如果有相等的比较则不交换，保证稳定性
在这里插入图片描述
注意在第五趟时候，此时没有交换，可以认为已经有序
在这里插入图片描述

算法实现

flag标记是否交换，如果没有交换则已经排序好了
总共n次循环，从0开始，每次循环
在这里插入图片描述

算法性能分析

有序的还需比对n次，都没交换才会得到这是有序的信息
最坏情况每次比对所比对的序列都是逆序的
交换元素一次需要比对元素三次
在这里插入图片描述

稳定性

稳定的，在相等时不做交换

冒泡排序是否适用于链表

也适用的
将当前链表指针与其后面的指针的元素比较，如果当前的大于后面的，那么就交换
在这里插入图片描述
此时49和后面的比较，不需要交换
在这里插入图片描述
此时69也不需要与后面的交换
在这里插入图片描述
97需要与后面的交换
在这里插入图片描述还需要交换
在这里插入图片描述
依然需要交换
在这里插入图片描述
依然要交换
在这里插入图片描述
依然要交换
在这里插入图片描述
此时第一趟结束，然后继续这样从头开始

小结

在这里插入图片描述

文章来源:https://blog.csdn.net/llovewuzhengzi/article/details/135416593
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章