python实现冒泡排序

今日去参加了几次面试，发现有次让手写冒泡排序，虽然思路是有的，还是需要巩固一下，毕竟平时用的比较少。

比如我们声明一个数组：arr=[9 ,6, 7 ,4, 8, 2]
一、排序为递增数组序列：
则第0轮排序：我们把第一数字跟其他的数字进行比对，分别进行交换。

1、6 9 7 4 8 2
2、6 7 9 4 8 2
3、6 7 4 9 8 2
4、6 7 4 8 9 2
5、6 7 4 8 2 9

至此，我们找到了最大的数据，放到了数组的末尾

第1轮排序：

1、6 4 7 8 2 9
2、6 4 7 2 8 9

至此，我们找到了第二大的数据，放到了数组的末尾-1

第2轮排序：

1、4 6 7 2 8 9
2、4 6 2 7 8 9 

第3轮排序：

1、4 2 6 7 8 9

第4轮排序

1、2 4 6 7 8 9

所以我们可以总结出以下的规律：

1. N个数的数组，我们外层需要循环N-1次: 因为只要找到了前N-1的大数，那最小的数，必然放在最前面了。
2. 内层循环每次都会减少1，因为每轮排好的最大数，需要进行排除，同时还要排除掉自身。
   说明：比如第1轮的排序，我们需要排除掉自身（-1），排除掉已经排好的最大数9（最大数个数1个 = i个）

代码实现：

a = [9, 6, 7, 4, 8, 2]
n = len(a)
for i in range(0, n-1):
    print("第" + str(i) + "轮排序")
    for j in (range(0, n-i-1)):
        if a[j] > a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]
        print(a)

image.png

二、看排序算法的时间复杂度O(n)
我们常说的时间复杂度，其实是最坏时间复杂度，计算方式采用大O阶公式进行计算：时间复杂度计算，在此不再进行赘述。
那最坏的情况是数组：[9,8,7,6,4,2]
所以我们可以看到此具体实例中的比较次数：
第一次比较5次：
第二次比较4次；
第三次比较3次；
第四次比较2次；
第五次比较1次；

即 5 + 4 + 3 + 2 + 1 = 15次
此时我们将数组的个数设置为N，则时间复杂度计算为：
N-1 + N-2 + N -3 + .... + 1 = N(N-1) /2
根据大O阶公式计算出，冒泡排序的时间复杂度为 O(n^2)