算法---冒泡法
冒泡排序的基本思路
对所有相邻记录的值进行比较,如果符合条件,则将两者进行交换,最终达到有序化。
冒泡排序的基本步骤
- 比较相邻的元素,如果前一个比后一个大(升序),调换位置
- 对每一对响铃的元素进行重复的工作,每步完成后,最大的元素出现在末尾
- 对上步骤重复,直到数组有序
代码
class Solution:
def bubbling(self, arr):
n = len(arr)
for i in range(n):
for j in range(n - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
if __name__ == "__main__":
arr = [8, 0, 4, 6, 1, 2, 7, 3, 5, 9]
s = Solution()
res = s.bubbling(arr)
print(res)
冒泡排序的优化
在纸上自己一步一步演练的人就会发现一个问题,比如说上面的例子中,8到末尾之后,再次遍历的时候,前边元素并没有比8大的,但是还会判断8,这一步如何优化呢?
代码
class Solution:
def bubbling(self, arr):
n = len(arr)
for i in range(n):
for j in range(n - 1 - i): # 优化点在这一行
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
if __name__ == "__main__":
arr = [8, 0, 4, 6, 1, 2, 7, 3, 5, 9]
s = Solution()
res = s.bubbling(arr)
print(res)
那这就完了吗?还有没有优化的地方呢?其实我们在第二层for循环中加个打印可以看出,在经过几轮排序之后,其实已经有序了,但是依然完成了整个遍历
我们先来看下代码
再次优化代码
class Solution:
def bubbling(self, arr):
n = len(arr)
num = 0
for i in range(n):
flag = False
print("第%s次执行" % num)
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
flag = True
if not flag:
break
num += 1
return arr
if __name__ == "__main__":
arr = [8, 0, 4, 6, 1, 2, 7, 3, 5, 9]
s = Solution()
res = s.bubbling(arr)
print(res)
- 优化后的代码将 flag变量初始化为
False
,在内层循环中,如果发生元素交换,则将 flag置为True
,表示发生了交换操作。 - 在内层循环结束后,检查 flag的值,如果 flag为
False
,说明在这一轮比较中没有元素交换,列表已经有序,此时使用break
语句提前结束排序过程,避免不必要的比较操作。
这样的优化可以提高冒泡排序的性能,特别是对于部分有序的列表,避免进行多余的比较和交换操作,提升了代码的执行效率。
在代码中加了打印,我们做下对比,上面是加了标志位的,执行了5次就结束了,我们去掉标志位的代码看下,大家看到了吧,执行了10次