Python | 有趣的冒泡排序
引言喝汽水的时候,汽水中常常有许多小小的气泡,哗啦哗啦飘到上面来。这是因为组成小气泡的二氧化碳比水要轻,所以小气泡可以一点一点向上浮动。而我们的冒泡排序之所以叫做冒泡排序,正是因为这种排序算法的每一个元素都可以像小气泡一样,根据自身大小,一点一点向着数组的一侧移动。解决方案冒泡排序逻辑比较简单,易于理解。步骤大致如下:对存放原始数据的数组,按从前往后的方向进行多次扫描,每次扫描称为一趟。当发现相邻两个数据的次序与排序要求的大小次序不符合时,即将这两个数据进行互换。如果从小到大排序,这时,较小的数据就会逐个向前移动,好像气泡向上漂浮一样。生活中,我们在集体活动中站队时,第一次站队由于没有固定的位置,往往是大家先随便站成一排,然后再通过换位置的方式逐步形成高矮顺序,这就体现了冒泡排序的思想下面用画图来表示一下该过程:
通过观察我们不难发现,第一轮比较了4次,第二轮比较了3次,第三轮比较了2次,第四轮比较了1次。为什么每一轮相互比较的次数都减少了一次?因为在第一轮比较结束的时候,这一组数据中最大的数23已经下沉到最底,之后的每一轮比较的时候都不用再去比较23;第二轮比较结束的时候,次大的12也沉到了倒数第二的位置,跟23一样,在之后的每一轮比较中就不用再去比较12了。第三轮结束和第四轮结束的情况也是类似。由此我们可以发现冒泡排序的特点:冒泡排序把N个数通过N-1轮排序,升序排序时每一轮比较会把最大的数下沉到最底(降序排序则反之),所以相互比较的次数每一轮都会比前一轮少一次。下面我们用Python代码实现该算法:List = []lenth = len(List)for i in range(0,lenth):for j in range(i+1,lenth):if List[j] < List[i]:List[i] , List[j] = List[j] , List[i] #升序用>,降序用<return List实际使用该算法时我们会发现这样一个问题:由于每次比较没有记录,即使是一个完全有序的含有N个数的序列,程序也会运行N-1次。为了改善这种情况,我们可以通过标记flag来优化排序,当在双重循环还未循环完毕的时候,如果已经完成了排序,则通过标记flag达到结束的效果。代码如下:List = []lenth = len(List)for i in range(0,lenth):flag = 0for j in range(i+1,lenth):if List[j] < List[i]:List[i] , List[j] = List[j] , List[i] #升序用>,降序用<flag += 1if flag == 0:break结语本文简单介绍了一下冒泡排序的原理及优化方法。虽然该算法效率不高,但是每个算法都有合适的应用场景。实习编辑:李欣容稿件来源:深度学习与文旅应用实验室(DLETA)