常见排序算法之冒泡排序

系统管理员 2022-03-08 00:42 193阅读 0赞

以升序排序为例，冒泡排序的思想如下：

（1）对于一个要排序的数组，从数组中的第一个数开始，把它与第二个数进行比较，如果第一个数大于第二个数，则把两个数的位置互换；  
（2）接着用第二个数与第三个数进行比较，如果第二个数大于第三个数，则把两个数的位置互换；  
（3）将这种比较规则一直进行下去，直到比较完倒数第二个数与倒数第一个数，并确定了它俩的位置；  
（4）经过这样一轮比较后，数组中最大的数已经排在了数组的最后；  
（5）然后从头开始，按照与上文相同的比较规则再次进行比较，只不过比较结束的位置变成了倒数第三个数；  
（6）一直这样进行下去，直到比较结束的位置变成了数组中的第一个数，则冒泡排序完成。

对于长度为n的序列进行升序排序，一共要进行n-1轮比较，每轮中比较的次数随轮次的增加而递减。

简单总结如下：

（1）对序列当中的左右数依次进行比较，保证右边的数始终不小于左边的数；

（2）对序列中除最后一个数之外的所有数再次执行步骤（1）；

（3）对序列中除最后两个数之外的所有数再次执行步骤（1）；

······

（n-1）直到对序列中的前两个数执行步骤（1）

**Python实现的冒泡排序：**

# 定义冒泡排序函数
    def bubble_sort(L):
        length = len(L)
        for x in range(1,length):  # 外层循环确定一共要有多少轮比较，对长度为n的数组进行升序排序一共要进行n-1轮比较
            for i in range(0,length-x):  # 内层循环控制每轮比较中结束比较的位置，结束比较的位置从倒数第二个数逐渐前进到第一个数
                if L[i] > L[i+1]:
                    L[i],L[i+1] = L[i+1],L[i]  # 交换位置
        return L

这种冒泡排序算法的时间复杂度为O(n^2)，因为无论是什么样的输入数组，这种算法都要进行n-1轮共(n-1+1)\*(n-1)/2=n\*(n-1)/2次比较。

但是，当只需要一轮比较就能对输入数组中的所有数完成排序时，这种算法的效率就变得比较低。比如当输入数组类似\[4,1,2,3\]、\[1,4,2,3\]、\[1,2,4,3\]、\[1,2,3,4\]这些情况时。为提高算法性能，可对上述冒泡排序稍作改进：

**上述冒泡排序的改进：**

# 改进的冒泡排序算法
    def new_bubble_sort(L):
        length = len(L)
        
        for x in range(1,length):         
            stopped = True
            
            for i in range(0,length-x):   
                if L[i] > L[i+1]:
                    L[i],L[i+1] = L[i+1],L[i]
                    stopped = False
                    
            if stopped == True:
                break
        return L

改进的冒泡排序算法中添加了一个控制变量stopped，它用于控制内层循环的执行。当输入数组是一个只需要一轮比较就能对数组中的所有数完成排序的数组时，内层循环只会被执行两次，第二次执行内层循环后，break语句会直接跳出外层循环，从而达到提高算法性能的目的。对于只需要一轮比较就能对数组中的所有数完成排序的数组，改进的冒泡排序算法在两轮比较中一共执行(n-1)+(n-2)=2\*n-3次，其时间复杂度为O(n)。

此外，冒牌排序算法是一种稳定的排序算法，关于排序算法的稳定性可以参考：[https://www.cnblogs.com/hydor/p/3530593.html][https_www.cnblogs.com_hydor_p_3530593.html]

其他参考：

[https://www.cnblogs.com/jiqingwu/p/bubble\_sort\_analysis.html][https_www.cnblogs.com_jiqingwu_p_bubble_sort_analysis.html]

[https://blog.csdn.net/iechenyb/article/details/81941022][https_blog.csdn.net_iechenyb_article_details_81941022]

[https_www.cnblogs.com_hydor_p_3530593.html]: https://www.cnblogs.com/hydor/p/3530593.html
[https_www.cnblogs.com_jiqingwu_p_bubble_sort_analysis.html]: https://www.cnblogs.com/jiqingwu/p/bubble_sort_analysis.html
[https_blog.csdn.net_iechenyb_article_details_81941022]: https://blog.csdn.net/iechenyb/article/details/81941022