Python实现冒泡排序

  • Post author:
  • Post category:python


最近在学习Python,下面是我的一些笔记



冒泡排序


实现思路

: 使用双重for循环,内层变量为i, 外层为j,在内层循环中不断的比较相邻的两个值(i, i+1)的大小,如果i+1的值大于i的值,交换两者位置,每循环一次,外层的j增加1,等到j等于n-1的时候,结束循环

第一次看不懂很正常,不要灰心,下面是使用代码的实现

arr = [7, 4, 3, 67, 34, 1, 8]

def bubble_sort(arr):
    n = len(arr)
    for j in range(0, n - 1):
        for i in range(0, n - 1 - j):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]


bubble_sort(arr)
print(arr)  # [1, 3, 4, 7, 8, 34, 67]

关键点其实在双重for循环变量的配置,我们来分析一下

第一次循环: j = 0, i~n-2 range(0, n-1)

第二次循环: j = 1, i~n-3 range(0, n-1-1)

第三次循环: j = 2, i~n-4 range(0, n-1-1-1)

—> range(0, n-1-j)

理解这一点后,我们就可以换一种写法来实现了

def bubble_sort2(arr):
    for j in range(len(arr) - 1, 0, -1):  # [n-1, n-2, ....2, 1]
        for i in range(0, j):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]


bubble_sort2(arr)
print(arr)  # [1, 3, 4, 7, 8, 34, 67]


优化


写到这里我们发现,无论是第一种写法还是第二种写法,他的时间复杂度都是O(n ^ 2), 第二种写法也仅仅停留在优化样式的层面,并没有带来性能的提升,想象一下,如果我们输入的本来就是一个有序序列,其实只需要一次循环就够了,所以我们需要针对特殊情况进行优化

def bubble_sort3(arr):
    for j in range(len(arr)-1, 0, -1):
        count = 0
        for i in range(0, j):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                count += 1
        if count == 0:
            return


bubble_sort3(arr)
print(arr)  # [1, 3, 4, 7, 8, 34, 67]

我们在循环中定义了一个变量count,如果第一次循环后count没有变化,就说明输入的是有序序列,这时我们直接return退出循环,这时候的时间复杂度为O(n)

扩展知识:冒泡排序还是一种稳定性的算法,如果序列中出现两个相同的值的时候,无论选取最大值,还是最小值进行排序,最后两个相同值的前后位置都是不变的。



版权声明:本文为qq_33988065原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。