python之冒泡排序改进

拼搏现实的明天。 2022-05-17 06:25 214阅读 0赞

# 冒泡排序改进 #

**关注公众号“轻松学编程”了解更多。**

## 一、普通冒泡排序 ##

[22,3,1,6,7,8,2,5]
    普通冒泡排序
    思路：
    第一趟排序 从下标0开始，取出对应的值22
    22和3比较，22 > 3 ,22和3交换，
    交换后，22和1比较，22 > 1,22和1比较，
    最后22会排到最后,
    第一趟排序后列表变成
    [3,1,6,7,8,2,5，22]
    第二趟排序 从下标1开始，取出对应的值1
    3和1比较，3 > 1 , 3和1交换，
    以此类推，最后列表变成有序的了
    [1,2,3,5,6,7,8,22]
    
    这一整个过程就像一个水泡从低往上冒，
    越往后水泡就越大(列表后面的元素会逐渐比前面的大)

def bubble_sort(alist):
        for i in range(len(alist)):
            # 跳过后面已经排好序的元素
            for j in range(len(alist)-1-i):
                if alist[j] > alist[j+1]:
                    alist[j],alist[j+1] = alist[j+1],alist[j]
        return alist
    
    
    def main():
        print(bubble_sort([22, 3, 1, 6, 7, 8, 2, 5]))
     
    
    if __name__ == '__main__':
        main()

结果为：
    [1, 2, 3, 5, 6, 7, 8, 22]

## 二、冒泡排序改进(搅拌排序) ##

考虑极端的情况：有以下列表\[9,1,2,3,4,5,6,7,8\]，当把结果一趟排序后，9就会被排列表最后了，这时列表就已经是有序的了，这时就可以直接退出循环。

def bubble_sort(alist):
        list_len = len(alist)
        for i in range(list_len):
            # 定义一个swapped
            # 如果有元素交换过就置为True
            # 如果没有元素交换过就退出循环
    
            swapped = False
            for j in range(list_len-1-i):
                if alist[j] > alist[j+1]:
                    alist[j],alist[j+1] = alist[j+1],alist[j]
                    swapped = True
            # 搅拌排序
            # 从后面往前面检索，如果前面比后面的大，就交换
            if swapped:
                swapped = False
                # 由于上面已经有一个元素在最后排好序了，所以这时要减2
                for j in range(list_len - 2 - i,0,-1):
                    if alist[j] < alist[j - 1]:
                        alist[j], alist[j - 1] = alist[j - 1], alist[j]
                        swapped = True
            # 如果没有发生元素交换，就说明列表已经是有序的了
            # 这时可以直接退出循环
            if not swapped:
                return alist
    
    
    def main():
        print(bubble_sort([22, 3, 1, 6, 7, 8, 2, 5]))
        print(bubble_sort([5, 1, 2, 3, ]))
        print(bubble_sort([1, 2, 3, ]))
    
    
    if __name__ == '__main__':
        main()

结果为：
    [1, 2, 3, 5, 6, 7, 8, 22]
    [1, 2, 3, 5]
    [1, 2, 3]

## 三、对象排序 ##

### 1、重载大于号、小于号 ###

class Student:
        """ 学生类 """
    
        def __init__(self,name,age):
            self.name = name
            self.age = age
    
        # 重载等于号
        def __eq__(self, other):
            return self.age == other.age
    
        # 重载大于号
        def __gt__(self, other):
            return self.age > other.age
    
        # 重载小于号
        def __lt__(self, other):
            return self.age < other.age
    
        # 设置输出格式
        def __repr__(self):
            return f'{self.name}:{self.age}'
    
    
    def bubble_sort(alist):
        list_len = len(alist)
        for i in range(list_len):
            # 定义一个swapped
            # 如果有元素交换过就置为True
            # 如果没有元素交换过就退出循环
    
            swapped = False
            for j in range(list_len-1-i):
                if alist[j] > alist[j+1]:
                    alist[j],alist[j+1] = alist[j+1],alist[j]
                    swapped = True
            # 搅拌排序
            # 从后面往前面检索，如果前面比后面的大，就交换
            if swapped:
                swapped = False
                # 由于上面已经有一个元素在最后排好序了，所以这时要减2
                for j in range(list_len - 2 - i,0,-1):
                    if alist[j] < alist[j - 1]:
                        alist[j], alist[j - 1] = alist[j - 1], alist[j]
                        swapped = True
            # 如果没有发生元素交换，就说明列表已经是有序的了
            # 这时可以直接退出循环
            if not swapped:
                return alist
    
    
    def main():
        s1 = Student('xiaoming',23)
        s2 = Student('hong',20)
        s3 = Student('da', 12)
        # 对学生按年龄进行排序
        print(bubble_sort([s1,s2,s3]))
    
    
    if __name__ == '__main__':
        main()

### 2、增加一个函数参数 ###

Python中函数是“一等对象”。

函数可以赋值给变量。

函数可以作为函数的参数。

函数可以作为函数的返回值。

把函数设计成一等对象的语言也就是支持函数式编程的语言。

class Student:
        """ 学生类 """
    
        def __init__(self,name,age):
            self.name = name
            self.age = age
    
        # 设置输出格式
        def __repr__(self):
            return f'{self.name}:{self.age}'
    
    # 可以使用":"来提示参数类型，"->"提示返回值类型，对函数没有影响
    def bubble_sort(alist:list,comp=None) -> list:
        ''' 冒泡排序 :param alist: 要进行排序的列表 :param comp: 比较函数 :return: 排好序的列表 '''
        list_len = len(alist)
        for i in range(list_len):
            swapped = False
            for j in range(list_len-1-i):
                # 如果传入了比较函数就使用比较函数
                comp_result = comp(alist[j],alist[j+1]) > 0 if comp else alist[j] > alist[j+1]
                if comp_result:
                    alist[j],alist[j+1] = alist[j+1],alist[j]
                    swapped = True
            # 搅拌排序
            # 从后面往前面检索，如果前面比后面的大，就交换
            if swapped:
                swapped = False
                # 由于上面已经有一个元素在最后排好序了，所以这时要减2
                for j in range(list_len - 2 - i,0,-1):
                    # 如果传入了比较函数就使用比较函数
                    comp_result = comp(alist[j], alist[j - 1]) < 0 if comp else alist[j] < alist[j - 1]
    
                    if comp_result:
                        alist[j], alist[j - 1] = alist[j - 1], alist[j]
                        swapped = True
            # 如果没有发生元素交换，就说明列表已经是有序的了
            # 这时可以直接退出循环
            if not swapped:
                return alist
    
    
    def compare(s1,s2) -> int:
         ''' 比较两个学生对象(规则: 先比年龄, 年龄相同比名字) :param s1: 待比较的第一个学生 :param s2: 待比较的第二个学生 :return: 如果s1小于等于s2返回负数; 如果s1大于s2返回正数; '''
         if s1.age == s2.age:
             return -1 if s1.name <= s2.name else 1
         else:
             return -1 if s1.age <= s2.age else 1
    
    
    def main():
        s1 = Student('xiaoming',23)
        s2 = Student('hong',20)
        s3 = Student('lan', 12)
        # 对学生按年龄进行排序
        print(bubble_sort([s1,s2,s3],comp=compare))
        
        list2 = ['grape', 'pitaya', 'pear', 'waxberry', 'apple']
        # 一句话就能写完的函数可以直接使用Lambda函数(匿名函数)
        # 根据字符串的长度给字符串排序
        print(bubble_sort(list2, lambda s1, s2: len(s1) - len(s2)))
    
    
    
    if __name__ == '__main__':
     main()

结果为：
    [lan:12, hong:20, xiaoming:23]
    ['pear', 'grape', 'apple', 'pitaya', 'waxberry']

## 后记 ##

【后记】为了让大家能够轻松学编程，我创建了一个公众号【轻松学编程】，里面有让你快速学会编程的文章，当然也有一些干货提高你的编程水平，也有一些编程项目适合做一些课程设计等课题。

也可加我微信【1257309054】，拉你进群，大家一起交流学习。  
如果文章对您有帮助，请我喝杯咖啡吧！

公众号

![公众号][20200317124808234.jpg]

![赞赏码][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xtX2lzX2Rj_size_16_color_FFFFFF_t_70]

关注我，我们一起成长~~

[20200317124808234.jpg]: /images/20220517/057190089e4d4ea2b9202dd4a4a31051.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xtX2lzX2Rj_size_16_color_FFFFFF_t_70]: /images/20220517/5e4ccb45a29547c394bf3c048149ca02.png