冒泡排序

题目：对给定一个数组进行排序。

思想：比较两个相邻元素，如果它们的顺序错误，就把它们交换位置。

原理: 每一趟只能将一个数归位, 如果有n个数进行排序,只需将n-1个数归位, 也就是说要进行n-1趟操作(已经归位的数不用再比较)

缺点: 冒泡排序解决了桶排序浪费空间的问题, 但是冒泡排序的效率特别低

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

实现：

"""
冒泡排序
"""
def bubbleSort(nums):
    for i in range(len(nums)-1):    # 这个循环负责设置冒泡排序进行的次数
        for j in range(len(nums)-i-1):  # ｊ为列表下标
            print(nums, 
                  "i={}/{}".format(i, len(nums)-1), 
                  "j={}/{}".format(j, len(nums)-i-1), 
                  "比较：", nums[j], nums[j+1])
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums

nums = [5,2,45,6,8,2,1]
print(bubbleSort(nums))

[5, 2, 45, 6, 8, 2, 1] i=0/6 j=0/6 比较： 5 2
[2, 5, 45, 6, 8, 2, 1] i=0/6 j=1/6 比较： 5 45
[2, 5, 45, 6, 8, 2, 1] i=0/6 j=2/6 比较： 45 6
[2, 5, 6, 45, 8, 2, 1] i=0/6 j=3/6 比较： 45 8
[2, 5, 6, 8, 45, 2, 1] i=0/6 j=4/6 比较： 45 2
[2, 5, 6, 8, 2, 45, 1] i=0/6 j=5/6 比较： 45 1
[2, 5, 6, 8, 2, 1, 45] i=1/6 j=0/5 比较： 2 5
[2, 5, 6, 8, 2, 1, 45] i=1/6 j=1/5 比较： 5 6
[2, 5, 6, 8, 2, 1, 45] i=1/6 j=2/5 比较： 6 8
[2, 5, 6, 8, 2, 1, 45] i=1/6 j=3/5 比较： 8 2
[2, 5, 6, 2, 8, 1, 45] i=1/6 j=4/5 比较： 8 1
[2, 5, 6, 2, 1, 8, 45] i=2/6 j=0/4 比较： 2 5
[2, 5, 6, 2, 1, 8, 45] i=2/6 j=1/4 比较： 5 6
[2, 5, 6, 2, 1, 8, 45] i=2/6 j=2/4 比较： 6 2
[2, 5, 2, 6, 1, 8, 45] i=2/6 j=3/4 比较： 6 1
[2, 5, 2, 1, 6, 8, 45] i=3/6 j=0/3 比较： 2 5
[2, 5, 2, 1, 6, 8, 45] i=3/6 j=1/3 比较： 5 2
[2, 2, 5, 1, 6, 8, 45] i=3/6 j=2/3 比较： 5 1
[2, 2, 1, 5, 6, 8, 45] i=4/6 j=0/2 比较： 2 2
[2, 2, 1, 5, 6, 8, 45] i=4/6 j=1/2 比较： 2 1
[2, 1, 2, 5, 6, 8, 45] i=5/6 j=0/1 比较： 2 1
[1, 2, 2, 5, 6, 8, 45]