冒泡排序

说到排序，最简单的思路就是：先找出数组中最小的元素，放到最前面，然后从第二个元素开始继续这一过程，这就是选择排序：

  1. def sort(our_list):
  2.     n=len(our_list)
  3.     for i in range(n):
  4.         for j in range(i+1,n):
  5.             if our_list[i]>our_list[j]:
  6.                 our_list[i],our_list[j]=our_list[j],our_list[i]
  1. a=[9,3,2,6,8,4,7,1,5]
  2. sort(a)
  3. print(a)
  5. >>> [1, 2, 3, 4, 5, 6, 7, 8, 9]

冒泡排序其实跟选择排序的思路有点类似，但冒泡排序是比较相邻两元素大小，第n轮中，数组第n大的元素一定能被确定。

  1. def bubble_sort(our_list):
  2.     n=len(our_list)
  3.     for i in range(n):
  4.         for j in range(n-1):
  5.             if our_list[j]>our_list[j+1]:
  6.                 our_list[j],our_list[j+1]=our_list[j+1],our_list[j]

但冒泡排序可以进一步优化：第n轮中，数组至少后n位元素已经确定，也可能后面有更多的元素处于顺序状态，可以考虑加个边界标记。

  1. def bubble_sort(our_list):
  2.     n=len(our_list)
  3.     border=n-1
  4.     for i in range(n):
  5.         max_index=0
  6.         for j in range(border):
  7.             if our_list[j]>our_list[j+1]:
  8.                 our_list[j],our_list[j+1]=our_list[j+1],our_list[j]
  9.                 max_index=j
  10.         border=max_index

对于 A=[1,2,3,4,6,5] 的情况，未优化的冒泡排序需要执行 5+4+3+2+1=15 次，而优化后的只要 5+4=9 次

冒泡排序 - 图1