1 '''
2 冒泡排序算法及其优化
3 冒泡排序的基本特征是只能交换相邻的元素。
4 从下边界开始，一趟扫描下来，可以把当前最大值顶到上边界；
5 如果没有发生交换操作，则表示数组是有序的。
6 '''
7
8
9 # 算法一：基本冒泡排序
10 def BubbleSort_1(arr):
11 # 外层循环累计排序轮数，同时控制待排序数组的上边界，即A[0..i]为待排序部分
12 # 内层循环扫描A[0..i-1]，比较相邻元素，并通过交换元素值的方式将最大值顶到最上方
13 for i
in range(len(arr) - 1, 0, -1
):
14 for j
in range(i):
15 if arr[j] > arr[j + 1
]:
16 arr[j], arr[j + 1] = arr[j + 1
], arr[j]
17 print(
'第%d次排序结果：'%(8-i),end=
'')
18 for j
in range(len(arr)):
19 print(
'='%
arr[j])
20
21
22 # 算法二：冒泡排序改进，设置交换操作标志
23 def BubbleSort_2(arr):
24 for i
in range(len(arr) - 1, 0, -1
):
25 Flag = False
# 先假设未做交换操作
26 for j
in range(0, i):
27 if arr[j] > arr[j + 1
]:
28 arr[j], arr[j + 1] = arr[j + 1
], arr[j]
29 Flag = True
# 设置交互操作标志
30 if not Flag:
31 break # 无交换操作，表示已完成排序，退出循环
32
33
34 # 算法二：双向冒泡(鸡尾酒排序)，因为未发生交换操作的区域是有序的，故每轮扫描下来可以更新上下边界，减少扫描范围
35 def BubbleSort_3(arr):
36 low, high = 0, len(arr) - 1
37 while low <
high:
38 swapPos = low
# 先假设最后一次发生交换操作的位置为low
39 for j
in range(low, high):
# 顺序扫描A[low..high-1]
40 if arr[j] > arr[j + 1
]:
41 arr[j], arr[j + 1] = arr[j + 1
], arr[j]
42 swapPos =
j
43 high = swapPos
# 修改待排序数组的上界为最后一次发生交换操作的位置
44 for j
in range(high, low, -1):
# 逆序扫描A[low+1..high]
45 if arr[j] < arr[j - 1
]:
46 arr[j], arr[j - 1] = arr[j - 1
], arr[j]
47 swapPos =
j
48 low = swapPos
# 修改待排序数组的下界为最后一次发生交换操作的位置
转载于:https://www.cnblogs.com/liangxfng/p/11537391.html
