亲宝软件园·资讯

展开

Python 算法之冒泡排序

船长博客 人气:0

冒泡排序基本思想

对于列表a依次比较两个相邻元素的大小,若a[j]大于a[j+1]则进行交换,第一趟把最大的数换到最后,依次类推生成有序的列表。
N个元素的列表要排序完成,需N-1趟排序(例:如果N是3(a = [10,5,2]),那么需要2趟依次把10和5进行移动生成有序列表[2,5,10])。
每一趟排序,就会少比较一次,因为每进行一趟排序都会找出余下列表中的一个较大值
每i趟的排序次数为(N-i-1)次,可以用双重循环语句,外层控制循环多少趟,内层控制每一趟的循环次数。

冒泡排序默认升序排列,如果需要降序则把内层循环中的>号改成<号

a = [10,5,2,4,1,0]
c = 0
print("        %s" % a)
for i in range(len(a)-1):
    print("Outer Loop:%d" % i)
    for j in range(len(a)-1-i):
        print("    Inner Loop:%d" % j)
        if a[j] > a[j+1]:
            a[j+1], a[j] = a[j], a[j+1]
        print("        %s" % a)
        c += 1
print(c)

输出结果:

        [10, 5, 2, 4, 1, 0]
Outer Loop:0
    Inner Loop:0
        [5, 10, 2, 4, 1, 0]
    Inner Loop:1
        [5, 2, 10, 4, 1, 0]
    Inner Loop:2
        [5, 2, 4, 10, 1, 0]
    Inner Loop:3
        [5, 2, 4, 1, 10, 0]
    Inner Loop:4
        [5, 2, 4, 1, 0, 10]
Outer Loop:1
    Inner Loop:0
        [2, 5, 4, 1, 0, 10]
    Inner Loop:1
        [2, 4, 5, 1, 0, 10]
    Inner Loop:2
        [2, 4, 1, 5, 0, 10]
    Inner Loop:3
        [2, 4, 1, 0, 5, 10]
Outer Loop:2
    Inner Loop:0
        [2, 4, 1, 0, 5, 10]
    Inner Loop:1
        [2, 1, 4, 0, 5, 10]
    Inner Loop:2
        [2, 1, 0, 4, 5, 10]
Outer Loop:3
    Inner Loop:0
        [1, 2, 0, 4, 5, 10]
    Inner Loop:1
        [1, 0, 2, 4, 5, 10]
Outer Loop:4
    Inner Loop:0
        [0, 1, 2, 4, 5, 10]
15
冒泡算法时间复杂度:
最优时间复杂度O(n) :正序情况,只需要一次外层循环,n-1次比较
最坏时间复杂度O(n2):逆序情况,需要n-1一次外层循环,每i趟外层循环执行n-1-i次内层循环

加载全部内容

相关教程
猜你喜欢
用户评论