冒泡排序是是一种比较基础简单的算法。
它的原理是通过对比前后的元素大小，将较大的数换到后面的方式来实现排序 。
排序过程
举个例子：
假如现在有一个无序数组disorder_arr = [4,2,19,10,-1]。
第一步：
取第0个元素4，和第1个元素2
对比，发现4比2大。
第二步：
交换4与2的索引。
即第0个元素为2,第1个元素为4，disorder_arr =[2,4,19,10,-1]
第三步：
取第1个元素4，和第2个元素19
对比，发现4小于19。
第四步：
保持索引不变。
重复上面步骤
遍历n-1次数组，会将数组中最大的数换到数组最后面的位置。
然后重头开始遍历，遍历n-2次数组。
为什么是n-2次呢？
因为最大的数已经在最后了，不需要再判断多一次了，
所以是n-2次。
这次会将第二大的数放置在倒数第二个索引上。
写一段代码
代码依然是使用Python3实现的
普通实现
通常所见到的冒泡排序都是这种实现，用了两层循环。
时间复杂度为O(n^2)
def bubble(self, disorder_arr: list):
for i in range(len(disorder_arr)): # 遍历n次数组
for j in range(len(disorder_arr) - i - 1): # 遍历n-i-1个数组的元素
if disorder_arr[j] > disorder_arr[j + 1]: # 对比当前数与下一个数
temp = disorder_arr[j]
disorder_arr[j] = disorder_arr[j + 1]
disorder_arr[j + 1] = temp
return disorder_arr
一个for的实现
还有一个比较特别的实现，只用了一层循环
def bubble2(self, disorder_arr: list):
team = len(disorder_arr) - 1
i = 0
while i < team: # 遍历n-1个元素，直到team等于i，即team=0
if disorder_arr[i] > disorder_arr[i + 1]: # 对比当前数与下一个数
temp = disorder_arr[i]
disorder_arr[i] = disorder_arr[i + 1]
disorder_arr[i + 1] = temp
if i == team - 1: # 如果遍历到了最后一个元素，则重置i的值，并给team减1
i = -1
team -= 1
i += 1
return disorder_arr
乍一看，感觉时间复杂度是O(n)
但玄机在于循环下面的if i == team - 1:这个判断，
当遍历到数组末尾的时候，会将i的值重置，
因此这个实现的时间复杂度依然是O(n^2)
分析
在冒泡排序中，首先需要遍历n-1次数组，然后要执行n次这种操作。
因此它的时间复杂度为O(n^2)
那么它是一个稳定的算法吗？
如果进行比较的时候，两个数相等，那么算法将不会对他们进行交换索引，
因此它是稳定的。
以上代码已上传至[github][https://github.com/alisen39/algorithm/blob/master/algorithms/sorting/bubbleSort.py]
欢迎大家友好交流[握手]
网友评论