冒泡排序及其优化

冒泡排序

一、思路

1、在数组[0,n)上

2、从i=0开始，不断比较list[i]与list[i+1],顺序的话不做调整；逆序的话交换二者位置。

3、i+1

4、当i = n-2时，1次遍历结束，最大值到了正确位置

5、在剩余数组中继续进行上述遍历过程

二、实现

嵌套代码编写过程中循环体，先用pass占位，减小思维复杂度

from sort_helper import test_sort,random_arraydef bubble_sort(array):"""冒泡排序的经典实现"""n = len(array)#子过程运行闭区间的右端点标记定义为i,范围[n-1,1],转换为适合while惯用区间为[n-1,0)i = n-1while i > 0:#子过程交换位置标记定义为j，范围为[0,i-1]，转换为适合while惯用区间为[0，i)#子过程运行区间为[0,i]j = 0while j < i:if array[j] > array[j+1]:array[j],array[j+1] = array[j+1],array[j]j += 1i -= 1return arrayif __name__ == '__main__':array = random_array()test_sort('bubble_sort', bubble_sort, array)

三、优化

• 冒泡排序的子过程没有提前中断机制（对比插入排序），所以子数组中每个元素都要遍历，交换又比较耗时；最终，导致算法性能较低。

• 但是相比于其他排序算法，冒泡排序子过程中对子数组中每个元素与其后缀元素进行了比较，这个特殊的过程可以作为优化点（选择排序则无此优势）

• 优化的数学依据：对于序列A,若任意Ai < Ai+1,则序列A有序

• 一旦判断子过程有序，则终止全部循环！

#性能改进 def bubble_sort1(array):"""冒泡排序的经典实现"""n = len(array)#子过程运行闭区间的右端点标记定义为i,范围[n-1,1],转换为适合while惯用区间为[n-1,0)i = n-1while i > 0:stop = True#子过程交换位置标记定义为j，范围为[0,i-1]，转换为适合while惯用区间为[0，i)#子过程运行区间为[0,i]j = 0while j < i:if array[j] > array[j+1]:array[j],array[j+1] = array[j+1],array[j]stop = Falsej += 1if stop:breaki -= 1return array #代码改进 def bubble_sort2(array):"""冒泡排序的经典实现"""n = len(array)stop = False#子过程运行闭区间的右端点标记定义为i,范围[n-1,1],转换为适合while惯用区间为[n-1,0)i = n-1while i > 0 and not stop:stop = True#子过程交换位置标记定义为j，范围为[0,i-1]，转换为适合while惯用区间为[0，i)#子过程运行区间为[0,i]j = 0while j < i:if array[j] > array[j+1]:array[j],array[j+1] = array[j+1],array[j]stop = Falsej += 1i -= 1return array

测试用例

if __name__ == '__main__':array1 = random_array()array2 = array1[:]array3 = nearly_ordered_array(10000, 1)array4 = array3[:]array5 = random_array(10000,0,1)array6 = array3[:]test_sort('bubble_sort random_array', bubble_sort, array1)test_sort('bubble_sort1 random_array', bubble_sort1, array2)test_sort('bubble_sort nearly_ordered_array', bubble_sort, array3)test_sort('bubble_sort1 nearly_ordered_array', bubble_sort1, array4)print('大量重复元素')test_sort('bubble_sort ', bubble_sort, array5)test_sort('bubble_sort1 ', bubble_sort1, array6)

数组有序性越强，优化效果越好

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的冒泡排序及其优化的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。