单向链表冒泡排序（单链表的冒泡排序）



       冒泡排序的基本思想是通过反复比较相邻的元素并交换它们的位置，将最大（或最小）的元素逐步 “冒泡” （移动）到数组的一端。就好像水中的气泡，较轻的气泡会逐渐往上浮，在排序中，较大（或较小）的值会逐渐移到数组的合适位置。

排序前：

       假设有一个包含 n 个元素的数组 arr，需要对其进行排序（这里以升序排序为例，若要实现降序排序，只需将比较条件反转即可）。

第一轮排序：

        1、从数组的第一个元素 arr [0] 开始，比较相邻的两个元素，即比较 arr [0] 和 arr [1]。如果 arr [0] 大于 arr [1]，那么就交换这两个元素的位置，使得较小的元素在前，较大的元素在后。如果 arr [0] 小于或等于 arr [1]，则不进行交换，继续比较下一对相邻元素。

        2、接着比较 arr [1] 和 arr [2]，按照上述比较和交换的规则进行操作。

        3、以此类推，依次比较 arr [2] 和 arr [3]、arr [3] 和 arr [4]…… 直到比较完 arr [n - 2] 和 arr [n - 1]。

        4、经过这一轮对数组中所有相邻元素的比较和交换操作后，数组中最大的元素就会 “冒泡” 到数组的末尾，即 arr [n - 1] 的位置。

第二轮排序：

        1、由于第一轮排序已经确定了数组中的最大元素在末尾位置，所以在第二轮排序时，只需对数组中除了最后一个元素（也就是已经排好序的最大元素）之外的剩余 n - 1 个元素进行操作。

        2、同样从第一个元素开始，即比较 arr [0] 和 arr [1]，根据比较结果决定是否交换。

        3、以此类推，依次比较 arr [1] 和 arr [2]、arr [2] 和 arr [3]…… 直到比较完 arr [n - 3] 和 arr [n - 2]。

        4、经过这一轮排序后，剩余元素中的最大元素会被移动到当前剩余元素的末尾，也就是 arr [n - 2] 的位置。

重复操作：

        …… 以此类推，进行多轮排序

        每一轮排序都会将当前剩余元素中的最大元素移动到当前剩余元素的末尾，并且每一轮排序所针对的剩余元素数量会比上一轮少 1 个。

最后一轮排序：

        当进行到第 n - 1 轮排序时（因为总共 n 个元素，经过 n - 1 轮排序就能确定所有元素的位置，最后只剩一个元素没有排，一定有序），此时只需对数组中的前两个元素 arr [0] 和 arr [1] 进行比较和交换操作（如果需要的话）。

排序后：

        经过上述 n - 1 轮的排序操作后，整个数组就完成了排序，所有元素按照升序排列在数组中。总结来说，冒泡排序就是通过不断地比较相邻元素并根据需要进行交换，逐轮将数组中的最大元素移动到数组的末尾，直到整个数组排序完成。

动态演示图来源网站URL：https://visualgo.net

C语言代码实现如下：

平均时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：稳定

适用于数据量较小且对排序速度要求不高的情况下。

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/30976.html