1.排序算法（1）

1.冒泡排序介绍

属于交换排序
两两比较大小，交换位置

升序排列：
n个数从左到右依次排列，编号从0开始到n-1，开始比较：
第一轮：n个数全部比较，索引0和索引为1的数进行比较，如果a[0]大于a[1]，则交换二者，否则不交换。同理，a[1]和a[2]比较。以此类推，
        当a[n-2]和a[n-1]完成比较时，n-1索引为n个数中的最大值，共比较了n-1次。
第二轮：比较n-1个数，第一轮已将最大数移动至索引n-1上。重复第一轮的操作，循环减少一次，当a[n-3]和a[n-2]完成比较时，此轮完成，
        n-2索引为前n-1个数中最大值，共比较n-2次。
...
第n-1轮：经过前n-2轮的比较，此时从a[2]至a[n-1]已经升序排列好。故此轮只需要比较一次即可。

动态效果：https://www.runoob.com/w3cnote/selection-sort.html

2.代码实现

版本1：

lst = [2,5,23,6,0,78,68]
print(lst)
for i in range(len(lst)):
  for j in range(len(lst)-1-i):
    if lst[j] > lst[j+1]:
      lst[j],lst[j+1] = lst[j+1],lst[j]

print(lst)

# 运行结果
[2, 5, 23, 6, 0, 78, 68]
[0, 2, 5, 6, 23, 68, 78]

版本2：循环的次数和交换的次数进行统计

lst0 = 
[
[2,5,23,6,0,78,68],
[5,2,23,0,6,78,68]
]

lst = lst0[0]
print(lst)

count = 0  # 用于统计循环总次数
count_swap = 0  # 用于统计交换总次数

for i in range(len(lst)):
  for j in range(len(lst)-1-i):
    count += 1
    if lst[j] > lst[j+1]:
      lst[j],lst[j+1] = lst[j+1],lst[j]
      count_swap += 1

print('count = {}'.format(count))
print('count_swap = {}'.format(count_swap))
print(lst)

# 运行结果
[2, 5, 23, 6, 0, 78, 68]
count = 21
count_swap = 6
[0, 2, 5, 6, 23, 68, 78]

# 总结：无论初始数组排列如何，则都需要进行固定数值的交换和循环，可以考虑优化

版本3：添加一个flag标识位，防止提前出现满足条件情况，从而及时break，跳出循环

lst0 = 
[
[2,5,23,6,0,78,68],
[5,2,23,0,6,78,68],
[0,2 5,6,23,68,78]
]

lst = lst0[1]
print(lst)

count = 0  # 用于统计循环总次数
count_swap = 0  # 用于统计交换总次数

for i in range(len(lst)):
  flag = False
  for j in range(len(lst)-1-i):
    count += 1
    if lst[j] > lst[j+1]:
      lst[j],lst[j+1] = lst[j+1],lst[j]
      flag = True
      count_swap += 1

  if not flag:
    break

print('count = {}'.format(count))
print('count_swap = {}'.format(count_swap))
print(lst)

# 执行结果  lst[0][0]
[2, 5, 23, 6, 0, 78, 68]
count = 20
count_swap = 6
[0, 2, 5, 6, 23, 68, 78]

# 执行结果  lst[0][1]
[5, 2, 23, 0, 6, 78, 68]
count = 18
count_swap = 6
[0, 2, 5, 6, 23, 68, 78]

# 执行结果  lst[0][2]
[0, 2, 5, 6, 23, 68, 78]
count = 6
count_swap = 0
[0, 2, 5, 6, 23, 68, 78]

3.总结

1.冒泡法需要一轮轮比较
2.可以设定一个标记判断此轮是否有数据交换发生，如果没有发生交换，可以结束排序，如果发生排序，继续下一轮排序。
3.最差的排序情况是：初始顺序与目标顺序完全相反，遍历次数1,..n-1之和n(n-1)/2
4.最好排序情况是初始顺序与目标顺序完全相同，遍历次数n-1
5.时间复杂度O(n^2)