冒泡排序(python)

系统 1459 0

1.冒泡排序

1.1算法思想

冒泡排序是一种简单的排序算法。通过重复地遍历要排序的数列,一次比较两个元素,从最开始的一对到最后的一对(相当于一个长度为2的滑动窗口),如果它们的顺序错误(看从小到达排列还是从大到小排列)就把它们交换过来。如果是升序排列的话,每次遍历都会把最大值交换到最右边。然后重复这个过程,直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的头部,就像冒泡一样。

这个算法不需要额外的空间,空间复杂度为o(1),同时对n个数据要进行n-1次比较,才能将最大的数固定在数列尾部,所以要固定好n个数,需要进行(n-1)+(n-2)+……+1+0次操作,时间复杂度为o(n^2)

1.2算法过程

  1. 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
  3. 针对所有的元素重复以上的步骤,除了最后一个;
  4. 重复步骤1~3,直到排序完成。

1.3 python实现

            
              
                def
              
              
                bubbleSort
              
              
                (
              
              numList
              
                )
              
              
                :
              
              
    n 
              
                =
              
              
                len
              
              
                (
              
              numList
              
                )
              
              
                if
              
               n 
              
                ==
              
              
                0
              
              
                or
              
               n 
              
                ==
              
              
                1
              
              
                :
              
              
                return
              
               numList
    
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              n
              
                )
              
              
                :
              
              
                # i在这里起到一个类似于计数的作用,看目前有多少个数排好序了
              
              
                for
              
               j 
              
                in
              
              
                range
              
              
                (
              
              n
              
                -
              
              i
              
                -
              
              
                1
              
              
                )
              
              
                :
              
              
                # 由于目前数组中,有i+1个数已经固定到数组尾部,因此只要对前n-i-1对数进行比较即可
              
              
                if
              
               numList
              
                [
              
              j
              
                ]
              
              
                >
              
               numList
              
                [
              
              j
              
                +
              
              
                1
              
              
                ]
              
              
                :
              
              
                temp 
              
                =
              
               numList
              
                [
              
              j
              
                ]
              
              
                numList
              
                [
              
              j
              
                ]
              
              
                =
              
               numList
              
                [
              
              j
              
                +
              
              
                1
              
              
                ]
              
              
                numList
              
                [
              
              j
              
                +
              
              
                1
              
              
                ]
              
              
                =
              
               temp
    
              
                return
              
                numList


numList 
              
                =
              
              
                [
              
              
                3
              
              
                ,
              
              
                10
              
              
                ,
              
              
                7
              
              
                ,
              
              
                1
              
              
                ,
              
              
                3
              
              
                ,
              
              
                5
              
              
                ,
              
              
                6
              
              
                ,
              
              
                2
              
              
                ,
              
              
                6
              
              
                ]
              
              
                print
              
              
                (
              
              bubbleSort
              
                (
              
              numList
              
                )
              
              
                )
              
              
                # 输出结果为 :[1, 2, 3, 3, 5, 6, 6, 7, 10]
              
            
          

更多文章、技术交流、商务合作、联系博主

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧,狠狠点击下面给点支持吧,站长非常感激您!手机微信长按不能支付解决办法:请将微信支付二维码保存到相册,切换到微信,然后点击微信右上角扫一扫功能,选择支付二维码完成支付。

【本文对您有帮助就好】

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描上面二维码支持博主2元、5元、10元、自定义金额等您想捐的金额吧,站长会非常 感谢您的哦!!!

发表我的评论
最新评论 总共0条评论