网站维护预算,wordpress阅读数 显示k,wordpress手机端显示pc端,房地产最新消息14号公告算法之冒泡排序
冒泡排序Bubble Sort
交换排序相邻元素两两比较大小#xff0c;有必要则交换。元素越小或越大#xff0c;就会在数列中慢慢的交换并“浮”向顶端#xff0c;如同水泡咕嘟咕嘟往上冒。
核心算法
排序算法#xff0c;一般都实现为就地排序#xff0c;输出…算法之冒泡排序
冒泡排序Bubble Sort
交换排序相邻元素两两比较大小有必要则交换。元素越小或越大就会在数列中慢慢的交换并“浮”向顶端如同水泡咕嘟咕嘟往上冒。
核心算法
排序算法一般都实现为就地排序输出为升序扩大有序区减小无序区。图中红色部分就是增大的有序区反之就是减小的无序区每一趟比较中将无序区中所有元素依次两两比较升序排序将大数调整到两数中的右侧每一趟比较完成都会把这一趟的最大数推倒当前无序区的最右侧 nums [1, 9, 8, 5] # 定义一个nums变量
#length len(nums)j 0for j in range(3): # 定义一个for循环if nums[j] nums[j1]: # if判断索引0 大于 索引1nums[j], nums[j1] nums[j1], nums[j] # 就进行两两交换直到把最大一个数交换到列表尾端变成有序区print(nums) # 第一次交换完打印j 1
for j in range(2):if nums[j] nums[j1]:nums[j], nums[j1] nums[j1], nums[j]print(nums)# 返回结果[1, 8, 5, 9]
# 返回结果[1, 5, 8, 9]# 优化
nums [1, 9, 8, 5]
length len(nums)for i in range(length - 1):for j in range(length - 1 - i): # length - 1 - i 3 - 0 j 0 1 2if nums[j] nums[j1]:nums[j], nums[j1] nums[j1], nums[j]print(nums)# 先取出nums的长度length通过迭代length的值可以确定循环执行的范围。
# 返回结果[1, 5, 8, 9]nums [1, 9, 8, 5, 4, 3, 2, 7, 6]
length len(nums)for i in range(length - 1):for j in range(length - 1 - i): # length - 1 - i 3 - 0 j 0 1 2if nums[j] nums[j1]:nums[j], nums[j1] nums[j1], nums[j]print(nums) # 这个打印是打印循环每次执行的结果print(nums)# 返回结果[1, 5, 8, 9]图一 可以看到后4趟执行的结果是没有变化的就是执行了无用的循环。
# 优化nums [1, 9, 8, 5, 4, 3, 2, 7, 6]
length len(nums)
count 0 # 表示执行的次数
count_swap 0 # 表示交换的次数for i in range(length - 1):swapped False # 如果发生变化就是True没有发生变化才是Falsefor j in range(length - 1 - i): # length - 1 - i 3 - 0 j 0 1 2count 1if nums[j] nums[j1]:nums[j], nums[j1] nums[j1], nums[j]swapped Truecount_swap 1print(nums)if not swapped: # 条件判断如果没有发生交换break # break 终止循环print(nums)
print(count, count_swap)图二 上面代码执行结果。
# 最终代码nums [1, 9, 8, 5, 4, 3, 2, 7, 6] # 定义一个无序区
length len(nums) # nums的长度for i in range(length - 1): #循环与次数相关就是O(n) # i循环控制趟数swapped True # 用于终止循环的条件for j in range(length - 1 - i): #循环与次数相关就是O(n) # j循环控制比较有序区与无序区if nums[j] nums[j1]:nums[j], nums[j1] nums[j1], nums[j]swapped Falseif swapped: # 如果swapped的值是True就证明没有在进行交换了。break # 终止循环print(nums) # O(n * n) O(n**2) On方# 循环的时间复杂度是O(n), 双层循环的时间复杂度是On**2)也就是On方
# 返回结果[1, 2, 3, 4, 5, 6, 7, 8, 9]
