python:冒泡排序的实现,冒泡排序与选择排序的对比

系统 458 0

冒泡排序是一个排序算法。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端。

其核心是: 重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

应用场景:

小规模数据排序,队列从小到大排序

实例:

将下列列表从小到大进行排序

            
              List 
              
                =
              
              
                [
              
              
                1
              
              
                ,
              
              
                5
              
              
                ,
              
              
                7
              
              
                ,
              
              
                4
              
              
                ,
              
              
                9
              
              
                ]
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                0
              
              
                ,
              
              
                4
              
              
                )
              
              
                :
              
              
                for
              
               j 
              
                in
              
              
                range
              
              
                (
              
              
                0
              
              
                ,
              
              
                4
              
              
                -
              
              i
              
                )
              
              
                :
              
              
                if
              
               List
              
                [
              
              j
              
                ]
              
              
                >
              
               List
              
                [
              
              j
              
                +
              
              
                1
              
              
                ]
              
              
                :
              
              
            List
              
                [
              
              j
              
                ]
              
              
                ,
              
               List
              
                [
              
              j
              
                +
              
              
                1
              
              
                ]
              
              
                =
              
               List
              
                [
              
              j
              
                +
              
              
                1
              
              
                ]
              
              
                ,
              
               List
              
                [
              
              j
              
                ]
              
              
                print
              
              
                (
              
              List
              
                )
              
              
                #输出结果为[1, 4, 5, 7, 9]
              
            
          

现在我们获取用户数据来进行排序:

            
              
                def
              
              
                Order
              
              
                (
              
              self
              
                )
              
              
                :
              
              
                for
              
               i 
              
                in
              
               rang
              
                (
              
              
                0
              
              
                ,
              
               n
              
                -
              
              
                1
              
              
                )
              
              
                :
              
              
                for
              
               j 
              
                in
              
              
                range
              
              
                (
              
              
                0
              
              
                ,
              
              n
              
                -
              
              
                1
              
              
                -
              
              i
              
                )
              
              
                :
              
              
                if
              
               List
              
                [
              
              j
              
                ]
              
              
                >
              
               List
              
                [
              
              j
              
                +
              
              
                1
              
              
                ]
              
              
                :
              
              
                List
              
                [
              
              j
              
                ]
              
              
                ,
              
               List
              
                [
              
              j
              
                +
              
              
                1
              
              
                ]
              
              
                =
              
               List
              
                [
              
              j
              
                +
              
              
                1
              
              
                ]
              
              
                ,
              
               List
              
                [
              
              j
              
                ]
              
              
                print
              
              
                (
              
              List
              
                )
              
              
    
List 
              
                =
              
              
                list
              
              
                (
              
              
                input
              
              
                (
              
              
                'please input some numbers:'
              
              
                )
              
              
                )
              
              
n 
              
                =
              
              
                len
              
              
                (
              
              List
              
                )
              
              
Order
              
                (
              
              List
              
                )
              
            
          

代码解析:

1、定义一个函数Order,然后调用它

            
              
                def
              
              
                Order
              
              
                (
              
              
                )
              
              
                :
              
              
                pass
              
              

Order
              
                (
              
              
                )
              
            
          

2、获取用户输入,并将用户输入转化为列表;得到列表的长度

            
              
                def
              
              
                Order
              
              
                (
              
              self
              
                )
              
              
                :
              
              
                pass
              
              

List 
              
                =
              
              
                list
              
              
                (
              
              
                input
              
              
                (
              
              
                'please input your numbers:'
              
              
                )
              
              
                )
              
              
n 
              
                =
              
              
                len
              
              
                (
              
              List
              
                )
              
              
Order
              
                (
              
              List
              
                )
              
            
          

3、先使用内层循环,内层变量为 j ,在内层循环中从0号位开始,不断的比较相邻位的值的大小,即比较 j 与 j+1的大小,若 j 号位的值大于 j+1号位的值,则将两者的数值进行交换(因为题目要求是从小到大排列),重复进行,直到此列表最后两位比较结束。

此步实现的是 将该列表中最大的数放在最后一位

            
              
                def
              
              
                Order
              
              
                (
              
              self
              
                )
              
              
                :
              
              
                for
              
               j 
              
                in
              
              
                range
              
              
                (
              
              
                0
              
              
                ,
              
               n
              
                -
              
              
                1
              
              
                )
              
              
                :
              
              
                if
              
               List
              
                [
              
              j
              
                ]
              
              
                >
              
               List
              
                [
              
              j
              
                +
              
              
                1
              
              
                ]
              
              
                :
              
              
            List
              
                [
              
              j
              
                ]
              
              
                ,
              
               List
              
                [
              
              j
              
                +
              
              
                1
              
              
                ]
              
              
                =
              
               List
              
                [
              
              j
              
                +
              
              
                1
              
              
                ]
              
              
                ,
              
               List
              
                [
              
              j
              
                ]
              
              
                print
              
              
                (
              
              List
              
                )
              
               

List 
              
                =
              
              
                list
              
              
                (
              
              
                input
              
              
                (
              
              
                'please input your numbers:'
              
              
                )
              
              
                )
              
              
n 
              
                =
              
              
                len
              
              
                (
              
              List
              
                )
              
              
Order
              
                (
              
              List
              
                )
              
            
          

4、使用外层循环,外层变量为 i ,当外层循环为0时,执行的正是上述步骤,当外层循环 i =1时,内层循环的 j 的取值范围则变成了n-1-1,外层循环 i 次时,内层循环 j 的取值范围变成 n-1-i

外层循环每循环一次,外层的 i 增加1,当 i= n-1时,外层循环结束。

            
              
                def
              
              
                Order
              
              
                (
              
              self
              
                )
              
              
                :
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                0
              
              
                ,
              
               n
              
                -
              
              
                1
              
              
                )
              
              
                :
              
              
                for
              
               j 
              
                in
              
              
                range
              
              
                (
              
              
                0
              
              
                ,
              
               n
              
                -
              
              
                1
              
              
                -
              
              i
              
                )
              
              
                :
              
              
                if
              
               List
              
                [
              
              j
              
                ]
              
              
                >
              
               List
              
                [
              
              j
              
                +
              
              
                1
              
              
                ]
              
              
                :
              
              
            	List
              
                [
              
              j
              
                ]
              
              
                ,
              
               List
              
                [
              
              j
              
                +
              
              
                1
              
              
                ]
              
              
                =
              
               List
              
                [
              
              j
              
                +
              
              
                1
              
              
                ]
              
              
                ,
              
               List
              
                [
              
              j
              
                ]
              
              
                print
              
              
                (
              
              List
              
                )
              
               

List 
              
                =
              
              
                list
              
              
                (
              
              
                input
              
              
                (
              
              
                'please input your numbers:'
              
              
                )
              
              
                )
              
              
n 
              
                =
              
              
                len
              
              
                (
              
              List
              
                )
              
              
Order
              
                (
              
              List
              
                )
              
            
          

冒泡排序与选择排序的对比:

python:选择排序(打擂台法)的实现及实例

相同点:

都是通过一轮内循环找出所要排序数中的最值,然后将最值放在最前面或者最后面。

冒泡排序和选择排序的时间复杂度相同

不同点:
主要体现在对其他数(非最值)的处理上.

冒泡排序:通过相邻的两个数的比较, 根据需要决定是否将两个数互换位置, 然后将比较继续推进。如上文的实例中,要求从小到大排列,通过比较两个数的大小,将大数置换到右边。

选择排序: 选择排序使用标记最值所在位置的方式,查找最值过程中,不移动数的位置,最后一轮循环结束后,将最值标记的位置的数放置于顶端。

冒泡排序优缺点:

优点:比较简单,空间复杂度较低,是稳定的
缺点:效率慢

选择排序优缺点:

优点:一轮比较只需要换一次位置

缺点:效率慢,不稳定

(举例[6, 7, 6, 3, 9] 在第一轮选择后,第一个元素6会和3交换,那么原序列中的两个6的相对位置顺序就被破坏了)


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

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请请扫描上面二维码支持博主1元、2元、5元等您想捐的金额吧,狠狠点击下面给点支持吧

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