1. 冒泡排序的思想
重复遍历要排序的数列，每次比较两个位置的元素，如果不符合排序规则，则交换两个位置的元素，一直遍历到没有需要交换的元素后，排序才算完成。
2. 冒泡排序实现步骤
冒泡排序可以可以在顺序表或链表中实现，下面使用顺序表为例实现冒泡排序，排序规则为把一组数从小到大进行排列。
2-1 单个元素实现排序
假定target_list为[10,9,7,3,5,6,2,1,4]，要求使用冒泡排序将此列表的元素从小到大进行排列。
我们先从第一轮遍历开始研究，从索引为0的元素开始两两比较，如下图所示：索引为0-8，绿色箭头为游标。
冒泡排序.png
- 令数组的长度为n，则target_list的长度为9，索引为0-8【n = len(target_list) 】
- 设游标所在的索引位置为i【一开始在0索引位置】，开始遍历数组后，游标每次往后移动一个位置，每移动一次，对比 i 和 i + 1 位置元素的大小，如果位置i的元素比i + 1 位置的元素大，则交换两个元素的位置，反之不交换。
【上图中的10，由于每次比较都比后一个元素大，因此会不断的往后走，最终被排列在数组的末尾】 - 那么遍历的条件怎么写呢？是否是(0,n-1)【索引为0,n-1】?答案是否定的，因为
我们比较的是 i 和 i+1 位置的元素，因此游标只需要走到 n-2 的位置即可。而range函数范围左闭右开，因此遍历的条件为range(0,n-1)
#
'''单次遍历冒泡排序分析'''
n = len(target_list)
for i in range(n-1):
if target_list[i] > target_list[i+1]:
# 如果位置i的元素比i+1位置的元素大，则交换两个元素的位置
target_list[i],target_list[i+1] = target_list[i+1],target_list[i]
#
2-2 思路扩展到所有元素
知道了单个元素的冒泡排序原理后，我们就可以将其运用到所有元素上。那么我们是否需要所有元素都执行一次冒泡排序呢?可以，但没必要。因为当我们确定了n-1个元素的位置后，剩下的一个元素的位置就已经确定了，因此我们只需要遍历n-1次即可。
-
设 j 为遍历的次数，则 j 的范围为(0,n-1)
-
单个元素实现排序时，我们让游标从0索引位置一直走到n-2索引的位置，那么在对数组进行遍历排序每个元素时，是否在遍历每个元素时，游标都需要从0索引位置走到n-2索引的位置？答案是否定的，因为每遍历一次，就有一个元素的位置确定了，下一次遍历的元素就不再需要和这个元素进行位置对比，因此游标需要走的长度是不断减少的，那么减少多少呢?
-
由上表可得，遍历了n-1次后，我们便能确定n-1个元素的位置，确定了n-1个元素的位置后，剩下1个元素的位置也可以确定，即所有元素的位置都能确定。由此，每次i需要走的长度为n-1-j。
【这里可能不那么好理解，可以多画几个图，看每次游标需要走的长度是多少，就能理解了】
def bubble_sort(target_list):
n = len(target_list)
for j in range(n-1):
for i in range(n-j-1):
if target_list[i] > target_list[i+1]:
target_list[i],target_list[i+1] = target_list[i+1],target_list[i]
return target_list
2-3 代码优化
上面已经完成了冒泡排序的代码，但是如果给定的 target_list 本身就是一个从小到大排序的顺序列表呢？那跟无序列表一样遍历n-1次就没有任何意义了，因此为了提高最优情况下的代码效率，我们加入一个计数器count，遍历过程中，target_list[i]和target_list[i+1]每交换一次，则计数+1，如果没有发生交换，则说明这是个顺序列表，此时，就可以跳过遍历过程，这样就可以提高最优情况下的代码效率了。
def bubble_sort(target_list):
n = len(target_list)
for j in range(n-1):
# 加入计数器
count = 0
for i in range(n-j-1):
if target_list[i] > target_list[i+1]:
target_list[i],target_list[i+1] = target_list[i+1],target_list[i]
count += 1
# 如果count ==0，则结束循环
if count == 0:
return
return target_list
以上是用顺序表实现冒泡排序的思路和代码，小伙伴们也可以使用链表来实现冒泡排序，思路都差不多。
网友评论