排序算法-冒泡排序

一、排序原理

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

二、平均时间复杂度（n²）

三、代码实现

自定义的模块（CreateData ,Swap ）源码见上篇博客：https://www.cnblogs.com/zhuanjiao/p/11668586.html

 1 from Common.CreateData import createData
 2 from Common.Swap import swap
 3 
 4 
 5 def bubbleSort(lyst):
 6     n = len(lyst)
 7     while n > 1:
 8         i = 1
 9         while i < n:
10             if lyst[i] < lyst[i-1]:
11                 swap(lyst, i, i-1)
12                 print('交换  ', n, i, lyst)
13             else:
14                 print('未交换', n, i, lyst)
15             i += 1
16         n -= 1
17 
18 
19 bubbleSort(createData())

四、运行过程

五、最好情况下代码改进

最好情况就是数组按照升序排列的。上面的一般冒泡算法，数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的。

5.1 源码

 1 def bubbleSortWithTweak(lyst):
 2     n = len(lyst)
 3     while n > 1:
 4         swapped = False
 5         i = 1
 6         while i < n:
 7             if lyst[i] < lyst[i - 1]:
 8                 swap(lyst, i, i - 1)
 9                 swapped = True
10                 print('交换  ', n, i, lyst)
11             else:
12                 print('未交换', n, i, lyst)
13             i += 1
14         if not swapped: return
15         n -= 1
16 
17 
18 bubbleSortWithTweak([2, 34, 56, 78, 98, 99])

5.2 运行结果：

5.3分析：

　　布尔值swapped 标识记录交换的次数，swapped 为False，表示数据未进行交换，数据是顺序存储的。