栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Python

【Python】Python实现冒泡排序

Python 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【Python】Python实现冒泡排序

代码
# -*- coding: UTF-8 -*-
import random


def bubble_sort(array):
    n = len(array)  # 数组array的元素数量
    for i in range(n-1):  # i表示第几趟遍历数组的无序区,一共要遍历n-1趟
        for j in range(n-i-1):  # j表示数组无序区最右侧元素的索引
            if array[j] > array[j+1]:
                tmp = array[j]
                array[j] = array[j+1]
                array[j+1] = tmp
        print('第{}趟: {}'.format(i, array))
    return array


# bubble_sort()的升级版本,如果某一趟中没有发生交换,说明已完成冒泡排序,那就不继续后续的操作
def bubble_sort_new(array):
    n = len(array)  # 数组array的元素数量
    for i in range(n-1):  # i表示第几趟遍历数组的无序区,一共要遍历n-1趟(从第0趟开始)
        is_swap = False  # 标志位,如果该趟中发生元素交换,其值为True
        for j in range(n-i-1):  # j表示数组无序区最右侧元素的索引
            if array[j] > array[j+1]:
                tmp = array[j]
                array[j] = array[j+1]
                array[j+1] = tmp
                is_swap = True
        print('第{}趟: {}'.format(i, array))
        if not is_swap:  # 如果这一趟中没有发生元素交换,那就跳出循环
            break
    return array
        

def main():
    random_array = [random.randint(0, 100) for i in range(10)]  # 随机定义10个0-100之间的数字
    print('random_array: {}'.format(random_array))

    sorted_array = bubble_sort_new(random_array)
    print('sorted_array: {}'.format(sorted_array))


if __name__ == '__main__':
    main()
分析 最坏时间复杂度。

冒泡排序一共走了 n − 1 n-1 n−1趟,第0趟遍历了 n − 1 n-1 n−1次,第1趟遍历了 n − 2 n-2 n−2次,第2趟遍历了 n − 3 n-3 n−3次,…,第n-2趟遍历了 1 1 1次。
因此,冒泡排序总共遍历了
( n − 1 ) + ( n − 2 ) + ( n − 3 ) + . . . + 1 = n ∗ ( n − 1 ) 2 (n-1)+(n-2)+(n-3)+...+1=frac{n*(n-1)}{2} (n−1)+(n−2)+(n−3)+...+1=2n∗(n−1)​
次,所以它的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。

最好时间复杂度

如果数组是按照要求已经排好顺序的数组,那么只需要走1趟,遍历 n − 1 n-1 n−1次,所以它的时间复杂度是 O ( n ) O(n) O(n)。

稳定性

当两个元素相等时,冒泡排序不会对它们进行交换,因此冒泡排序是稳定的。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/892889.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号