您的位置： 首页 > 生活常识 >

冒泡法的实现原理是什么？（冒泡算法简介）

100次浏览     发布时间：2024-07-30 11:16:11    

算法原理

冒泡排序算法的原理如下：

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

简单示意图

时间复杂度

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C

和记录移动次数M均达到最小值：

C~min~ = n-1 , M~min~=0

所以，冒泡排序最好的时间复杂度为O(n)

若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-1次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

Cmax~=n(n-1)/2=O(n^2)

Mmax = 3n(n-1)/2=O(n^2)

算法实现

def fun1(list1):
    n = len(list1)
    count = 0
    while n > 1:
        for i in range(n-1):
            if list1[i] > list1[i+1]:
                list1[i], list1[i+1] = list1[i+1], list1[i]  # 如果大于就往后移动一位
                count += 1
        n -= 1  # n减去1,下次循环最后一个不用检测了
    print('共交换{}次'.format(count))
    return list1


list2 = [6, 5, 4, 3, 2, 1]
print(fun1(list2))
"""
# 输出报告
共交换15次
[1, 2, 3, 4, 5, 6]
"""

注意事项

  1. 冒泡算法每次都会把最大的数给输送到末尾，所以每次用于循环比较的次数都会减1
  2. 冒泡算法相对于普通二次循环遍历，减少了n/2的计算次数，减少了计算次数，但时间复杂度仍然为n^2^。关于时间复杂度与空间复杂度可以自行百度。
相关文章

网站内容来自网络，如有侵权请联系我们，立即删除！
Copyright © 笨百科 琼ICP备2025056076号-51