精华内容
下载资源
问答
  • Python实现冒泡排序

    万次阅读 多人点赞 2020-07-06 23:22:30
    Python实现冒泡排序

    Python实现冒泡排序

    一、冒泡排序简介

    冒泡排序(Bubble Sort)是一种常见的排序算法,相对来说比较简单。

    冒泡排序重复地走访需要排序的元素列表,依次比较两个相邻的元素,如果顺序(如从大到小或从小到大)错误就交换它们的位置。重复地进行直到没有相邻的元素需要交换,则元素列表排序完成。

    在冒泡排序中,值最大(或最小)的元素会通过交换慢慢“浮”到元素列表的“顶端”。就像“冒泡”一样,所以被称为冒泡排序。

    二、冒泡排序原理

    冒泡排序的原理如下:

    1. 比较相邻的两个元素。如果第一个比第二个大则交换他们的位置(升序排列,降序则反过来)。

    2. 从列表的开始一直到结尾,依次对每一对相邻元素都进行比较。这样,值最大的元素就通过交换“冒泡”到了列表的结尾,完成第一轮“冒泡”。

    3. 重复上一步,继续从列表开头依次对相邻元素进行比较。已经“冒泡”出来的元素不用比较(一直比较到结尾也可以,已经“冒泡”到后面的元素即使比较也不需要交换,不比较可以减少步骤)。

    4. 继续从列表开始进行比较,每轮比较会有一个元素“冒泡”成功。每轮需要比较的元素个数会递减,一直到只剩一个元素没有“冒泡”时(没有任何一对元素需要比较),则列表排序完成。

    以列表 [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] 进行升序排列为例。列表的初始状态如下图。

    要进行升序排列,则大的元素要依次“冒泡”到列表的结尾。

    1. 从列表的开头,比较相邻的两个元素,如果第一个值比第二个值大则交换。10小于17,不需要交换。

    2. 向列表的结尾方向“走访”,比较第二组相邻的元素(第二个和第三个),如果不是从小到大则交换。17小于50,不需要交换。

    3. 继续“走访”,比较第三组相邻的元素,如果不是从小到大则交换。50大于7,所以需要交换。

    4. 对顺序错误的元素进行位置交换。交换50和7的位置。

    5. 一直“走访”到结尾,第一轮“冒泡”结束后,值最大的元素“冒泡”到了列表的结尾。50“冒泡”到了列表结尾。

    在下一轮“冒泡”中,不需要再将50进行比较,需要比较的元素个数减1。

    6. 从列表开头,重复下一轮“冒泡”,每进行一轮“冒泡”,需要比较的元素都少一个,直到没有元素对需要比较时,整个列表排序完成。排序结果如下图。

    三、Python实现冒泡排序

    # coding=utf-8
    def bubble_sort(array):
        for i in range(1, len(array)):
            for j in range(0, len(array)-i):
                if array[j] > array[j+1]:
                    array[j], array[j+1] = array[j+1], array[j]
        return array
    
    
    if __name__ == '__main__':
        array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
        print(bubble_sort(array))

    运行结果:

    [5, 7, 10, 15, 17, 21, 24, 27, 30, 36, 45, 50]

    代码中,i 表示第几轮“冒泡”,j 表示“走访”到的元素索引。每一轮“冒泡”中,j 需要从列表开头“走访”到 len(array) - i 的位置。

    四、冒泡排序的时间复杂度和稳定性

    1. 时间复杂度

    在没有特殊说明时,一般都是计算最坏时间复杂度。

    在冒泡排序中,最坏的情况是元素列表的初始状态是完全逆序排列的,需要进行 n-1 轮“冒泡”,每一轮“冒泡”需要进行 n-i 次比较和交换操作。i 的平均值为 n/2 ,时间复杂度为 T(n)=n(n-1)/2 ,再乘每次操作的步骤数(常数,不影响大O记法),所以冒泡排序的时间复杂度为 O(n^2) 。

    2. 稳定性

    排序算法的稳定性指,当元素列表中有相等的元素时,相等元素的相对次序是否固定不变,如果相对次序固定不变,则排序算法是稳定的,反之。

    在冒泡排序中,每次比较两个元素,当元素的大小顺序错误时才会进行交换,如果元素列表中有两个相等的元素,它们最终肯定会相邻在一起,但对它们比较时不会进行交换,相对次序是保持不变的。所以冒泡排序是一种稳定的排序算法。

     

     

    展开全文
  • Python 实现冒泡排序

    2021-03-25 19:33:02
    Python实现冒泡排序欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居...

    Python实现冒泡排序

    冒泡排序,和其他语言一样使用两层for循环,直接上代码:

    data=[1,6,43,23,65,0,35]
    n=len(data)
    for i in range(0,n-1):
    	for j in range(0,n-1-i):
    		if data[j]>data[j+1] :
    			data[j],data[j+1]=data[j+1],data[j]
    print(data)
    		
    

    输出:
    在这里插入图片描述

    展开全文
  • python实现冒泡排序

    2019-08-10 23:26:17
    python实现冒泡排序 冒泡排序(从小到大排序): 冒泡排序的思路为拿第一个数与后面的数一一对比,如果前一个数比后一个数大那么将位置互换,这一经过一次可以使得最大的元素置于最后 如图排序数为:54 26 93 17 77 ...

    python实现冒泡排序

    冒泡排序(从小到大排序):

    冒泡排序的思路为拿第一个数与后面的数一一对比,如果前一个数比后一个数大那么将位置互换,这一经过一次可以使得最大的元素置于最后
    如图排序数为:54 26 93 17 77 31 44 55 20
    在这里插入图片描述
    如图所示,经过一次排序以后93跑到了最后一个位置,经过八次这样的循环便可得到排序后的数字

    def BubleSort(alist):
    	n=len(alsit)
    #第一次比较
        for i in range(n-1):#这里的循环只能是0——n-2,
        #我们知道n-1是最后一个数字,如果是n的话,那么alist[i+1]就是alist[n]是一个未知数了。
            if alist[i]>alist[i+1]:
            #如果前一个元素比后一个元素大,互换元素
                alist[i],alist[i+1]=alist[i+1],alist[i]
    

    但是我们是需要全部进行排序的,所以代码不可能这样子写,是需要两个for循环语句来实现的。
    我们就以排序数为:54 26 93 17 77 31 44 55 20 为例子。
    首先我们可以看出需要对其进行8次一次排序操作。
    (1)26 54 17 77 31 44 55 20 93
    (2)26 17 54 31 44 50 20 77 93
    (3)17 26 31 44 50 20 54 73 93
    (4)17 26 31 44 20 50 54 73 93
    (5)17 26 31 20 44 50 54 73 93
    (6)17 26 20 31 44 50 54 73 93
    (7)17 20 26 31 44 50 54 73 93
    (8)17 20 26 31 44 50 54 73 93
    那么我们设置第一个循环的话j就是从range(0,n-1)中去循环,那么第二个循环i是与第一个循环有关系的。
    例如当 j=0, i就要从0——n-2
    当j=1, i就要从0——n-3
    当j=2, i就要从0——n-4
    以此类推 就可以得到i是从range(0,n-1-j)中去循环。这里可以通过画图方式去理解。再每次j循环一次后,需要排序的数字就会少一个,(因为在每次的j循环最后一个元素都是最大的,无需在对后面的数字对比。)

    def BubleSort(alist):
        """冒泡排序""""
        n=len(alist)#记录表长
        for j in range(n-1):
            #执行的次数
            for i in range(0,n-1-j):
                #每一次循环一个一个比较前后元素的大小
                if alist[i]>alist[i+1]:
                    alist[i],alist[i+1]=alist[i+1],alist[i]#元素互换
    if __name__=="__main__":
        a=[54,26,93,17,77,31,44,55,20]
        print("排序之前的数为:")
        print(a)
        print("排序之后的数为:")
        BubleSort(a)
        print(a)
    
    
    

    时间复杂度:

     for j in range(n-1):
            for i in range(0,n-1-j):
                if alist[i]>alist[i+1]:
    

    这里面有两个循环,第一个循环执行次数为n-1,第二个循环是从 n-1,n-2,n-3 .。。。。。这一循环,所以两个循环的可以都看出n,所以最坏的复杂度为O(n*n),最优复杂度为O(n)。

    代码优化:

    对于本来就排序好的列表来说,我们没必要进行上面的代码,这样比较的话时间复杂度为O(n*n)。
    如[1,2,3,4,5,6] 如果按照上面的代码,我们需要执行两个for循环才可以。其实呢!没必须,因为这个本来就是排序好的列表了,那么我们优化代码如下

    def BubleSort(alist):
        """冒泡排序""""
        n=len(alist)#记录表长
        for j in range(n-1):
            #执行的次数
            count=0 #初始化计数变量
            for i in range(0,n-1-j):
                #每一次循环一个一个比较前后元素的大小
                if alist[i]>alist[i+1]:
                    alist[i],alist[i+1]=alist[i+1],alist[i]#元素互换
                    count+=1# 如果进行了交换就对count进行+1操作
                if 0==count:#如果count等于0就说明没有进行上面if条件里面的内容,也就是说没有交换
                    return
    if __name__=="__main__":
        a=[54,26,93,17,77,31,44,55,20]
        print("排序之前的数为:")
        print(a)
        print("排序之后的数为:")
        BubleSort(a)
        print(a)
    
    
    展开全文
  • python 实现冒泡排序

    2018-08-30 00:22:35
    python实现冒泡排序 # 1.按元素长度升序排列 def maopao1(strs): """ :type strs: List[str] """ for i in range(len(strs)-1): for j in range(i+1, len(strs)): if len...

    用python实现冒泡排序

    # 1.按元素长度升序排列
    
    def maopao1(strs):
        """
        :type strs: List[str]
        """
        for i in range(len(strs)-1):
            for j in range(i+1, len(strs)):
                if len(strs[i]) > len(strs[j]):
                    (strs[i], strs[j]) = (strs[j], strs[i])
                    """
                    temp = strs[i]
                    strs[i] = strs[j]
                    strs[j] = temp
                    """
        return strs
    
    ret1 = maopao1(["file", "newfile", "file_name", "fl", "", "1"])
    print(ret1)
    
    # 2.按元素数值大小升序排列
    
    def maopao2(strs):
        """
        :type strs: List[str]
        列表中存储数字
        """
        for i in range(len(strs)-1):
            for j in range(i+1, len(strs)):
                if strs[i] > strs[j]:
                    (strs[i], strs[j]) = (strs[j], strs[i])
                    """
                    temp = strs[i]
                    strs[i] = strs[j]
                    strs[j] = temp
                    """
        return strs
    
    ret2 = maopao2([3, 2, 55, 111, 0, 1])
    print(ret2)
    
    
    展开全文
  • 走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是...冒泡排序算法的运作如下:由于它的简洁,冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。以上是百...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,382
精华内容 952
关键字:

python实现冒泡排序

python 订阅