Python3排序算法01 - 冒泡排序

  • 原创
  • Madman
  • /
  • 2018-09-11 10:28
  • /
  • 0
  • 123 次阅读

Synopsis: 冒泡排序是一种极其简单的排序算法,它重复地走访过要排序的元素,依次比较相邻两个元素,如果他们的顺序错误就把他们调换过来,直到没有元素再需要交换,排序完成。由于它的简洁,冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。尽管冒泡排序是最容易了解和实现的排序算法之一,但它对于元素较多的序列排序时是很没有效率的

代码已上传到 https://github.com/wangy8961/python3-algorithms ,欢迎star

1. 算法介绍

冒泡排序(Bubble Sort)是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作会重复地进行,当不再有元素需要交换的时候,就表示数列排序完成了。冒泡排序与气泡上升的过程相似,气泡上升的过程中不断吸收空气而变大,冒泡排序算法也是依次比较相邻的两个元素,将较大的"浮"到最右边

Bubble Sort 01

算法(假设按升序排序)的主要步骤如下:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。步骤1和步骤2合称为一次冒泡操作,每次冒泡操作会选出 "未排序序列" 的最大值,所以总共需要进行n-1次冒泡操作
  3. 针对所有的元素重复以上的步骤,除了最后一个(第2次冒泡操作,序列的最后一个元素是 "已排序序列",该冒泡操作需要进行n-2次比较)
  4. 持续对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较(冒泡操作只针对 "未排序序列",所以每次冒泡操作的比较次数递减)

Bubble Sort 02

上图演示了第1次冒泡操作,该冒泡操作需要进行8次比较

2. Python实现

假设要排序拥有 n 个元素的列表L,且按升序排列

2.1 错误的算法

下面的代码只是演示错误的情形,每次冒泡操作都遍历整个序列,将当前元素与 "已排序序列" 中的元素进行比较完全是浪费时间:

def bubbLe_sort(L):
    '''演示错误的冒泡算法'''
    n = len(L)
    if n <= 1:
        return

    for i in range(n-1):  # 共需要n-1次冒泡操作

        # 每次冒泡操作都遍历整个列表的元素,即使后面已经排序好的元素也会比较,完全是在浪费时间
        for j in range(n-1):  # j 表示列表的下标,j不能取值n-1,否则L[j+1]会下标越界
            if L[j] > L[j+1]:
                L[j], L[j+1] = L[j+1], L[j]


if __name__ == '__main__':
    L1 = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print('Before: ', L1)
    bubbLe_sort(L1)
    print('After: ', L1)

    # Output:
    # Before:  [54, 26, 93, 17, 77, 31, 44, 55, 20]
    # After:  [17, 20, 26, 31, 44, 54, 55, 77, 93]

压力测试,使用 timeit 模块排序1000次,如果from __main__ import L,结果好像不对,所以在函数内初始化相同的L:

from timeit import timeit


def bubbLe_sort():
    # import random
    # gen = (random.randint(1, 100) for i in range(100))  # 产生100个 1-99 范围内的随机整数
    # L = list(gen)
    L = [96, 2, 65, 23, 47, 58, 8, 48, 69, 92, 34, 83, 93, 47, 45, 55, 95, 15, 92, 24, 64, 19, 29, 55, 35, 48, 39, 29, 63, 94, 99, 38, 50, 10, 10, 93, 74, 27, 74, 44, 29, 81, 85, 86, 74, 30, 50, 50, 12, 12, 38, 75, 41, 87, 80, 97, 16, 48, 65, 69, 83, 71, 28, 9, 64, 69, 27, 74, 74, 86, 40, 69, 79, 79, 77, 100, 53, 72, 77, 16, 8, 36, 41, 58, 59, 29, 46, 79, 81, 66, 8, 35, 60, 52, 2, 82, 2, 36, 79, 66]

    n = len(L)
    for i in range(n-1):
        for j in range(n-1):
            if L[j] > L[j+1]:
                L[j], L[j+1] = L[j+1], L[j]

    return L


print('Bubble sort function run 1000 times, cost: ', timeit('bubbLe_sort()', 'from __main__ import bubbLe_sort', number=1000), 'seconds.')

# Output
# Bubble sort function run 1000 times, cost:  2.900782099 seconds.

2.2 正确的算法

每次冒泡操作只针对 "未排序序列",所以每次冒泡操作的比较次数递减:

冒泡操作次数 比较的次数
第1次,i = 0 n-1
第2次,i = 1 n-2
第3次,i = 2 n-3
... ...
第n-1次,i = n-2 1

助记:每次冒泡操作需要 n-i-1 次比较

def bubbLe_sort(L):
    '''冒泡排序,升序'''
    n = len(L)
    if n <= 1:
        return

    for i in range(n-1):  # 共需要n-1次冒泡操作

        # 每次冒泡操作,只遍历并比较 "未排序的序列" 中的元素(会依次变少)
        # 注意 j 表示序列的下标,所以 j 的取值范围为 0, 1, 2 ... n-i-2, 不能取n-i-1,否则后续L[j+1]会下标越界
        for j in range(n-i-1):  # 助记:每次冒泡操作需要 n-i-1 次比较
            if L[j] > L[j+1]:  # 如果L[j]比L[j+1]大,则交换它们的位置
                L[j], L[j+1] = L[j+1], L[j]


if __name__ == '__main__':
    L1 = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print('Before: ', L1)
    bubbLe_sort(L1)
    print('After: ', L1)

    # Output:
    # Before:  [54, 26, 93, 17, 77, 31, 44, 55, 20]
    # After:  [17, 20, 26, 31, 44, 54, 55, 77, 93]

分析过程:

外层for循环中的变量i代表第几次冒泡操作,取值范围为0, 1, 2 ... n-2,对应range(n-1)。内层for循环中的变量j代表每次冒泡操作中的列表下标,因为每次冒泡操作中需要进行比较的列表元素范围会逐渐缩小,所以列表下标j的取值范围就应该不断变化:

  1. 第1次冒泡操作,i = 0时,下标j的取值范围为0, 1, 2 ... n-2,因为要比较L[j]L[j+1]的大小,所以j不能取n-1,否则L[j+1]将超出列表的下标范围(IndexError: list index out of range)
  2. 第2次冒泡操作,i = 1时,下标j的取值范围为0, 1, 2 ... n-3,因为第1次冒泡操作过后,第n个元素(即L[n-1])已经是列表的最大值,只需要对前n-1个元素进行冒泡操作即可
  3. 第3次冒泡操作,i = 2时,下标j的取值范围为0, 1, 2 ... n-4

所以下标j的取值范围为0, 1, 2 ... n-i-2,对应range(n-i-1)

每一次冒泡操作后的状态图如下:

Bubble Sort 03

压力测试:

from timeit import timeit


def bubbLe_sort():
    # import random
    # gen = (random.randint(1, 100) for i in range(100))  # 产生100个 1-99 范围内的随机整数
    # L = list(gen)
    L = [96, 2, 65, 23, 47, 58, 8, 48, 69, 92, 34, 83, 93, 47, 45, 55, 95, 15, 92, 24, 64, 19, 29, 55, 35, 48, 39, 29, 63, 94, 99, 38, 50, 10, 10, 93, 74, 27, 74, 44, 29, 81, 85, 86, 74, 30, 50, 50, 12, 12, 38, 75, 41, 87, 80, 97, 16, 48, 65, 69, 83, 71, 28, 9, 64, 69, 27, 74, 74, 86, 40, 69, 79, 79, 77, 100, 53, 72, 77, 16, 8, 36, 41, 58, 59, 29, 46, 79, 81, 66, 8, 35, 60, 52, 2, 82, 2, 36, 79, 66]

    n = len(L)
    for i in range(n-1):
        for j in range(n-i-1):
            if L[j] > L[j+1]:
                L[j], L[j+1] = L[j+1], L[j]

    return L


print('Bubble sort function run 1000 times, cost: ', timeit('bubbLe_sort()', 'from __main__ import bubbLe_sort', number=1000), 'seconds.')

# Output:
# Bubble sort function run 1000 times, cost:  1.853806487 seconds.

2.3 优化的算法

如果传入一个几乎已经按 "升序" 排列好的列表,章节2.2的代码还是会老老实实的执行两次完整的for循环,最优时间复杂度为O(n^2)如果我们在某一次冒泡操作中,内层遍历后发现没有交换任何元素位置,则说明此时列表已经是排序好了

Bubble Sort 04

def bubbLe_sort(L):
    '''优化后的冒泡排序,升序
    最优时间复杂度为O(n),比如L本身就是排好序的:[17, 20, 26, 31, 44, 54, 55, 77, 93]
    最坏时间复杂度还是O(n^2)
    '''
    n = len(L)
    if n <= 1:
        return

    for i in range(n-1):
        flag = False
        for j in range(n-i-1):
            if L[j] > L[j+1]:
                L[j], L[j+1] = L[j+1], L[j]
                flag = True
        if not flag:  # 如果我们在某一次冒泡操作中,内层遍历后发现没有交换任何元素位置,则说明此时列表已经是排序好了
            return


if __name__ == '__main__':
    L1 = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print('Before: ', L1)
    bubbLe_sort(L1)
    print('After: ', L1)

    # Output:
    # Before:  [54, 26, 93, 17, 77, 31, 44, 55, 20]
    # After:  [17, 20, 26, 31, 44, 54, 55, 77, 93]

压力测试:

from timeit import timeit


def bubbLe_sort():
    # import random
    # gen = (random.randint(1, 100) for i in range(100))  # 产生100个 1-99 范围内的随机整数
    # L = list(gen)
    L = [96, 2, 65, 23, 47, 58, 8, 48, 69, 92, 34, 83, 93, 47, 45, 55, 95, 15, 92, 24, 64, 19, 29, 55, 35, 48, 39, 29, 63, 94, 99, 38, 50, 10, 10, 93, 74, 27, 74, 44, 29, 81, 85, 86, 74, 30, 50, 50, 12, 12, 38, 75, 41, 87, 80, 97, 16, 48, 65, 69, 83, 71, 28, 9, 64, 69, 27, 74, 74, 86, 40, 69, 79, 79, 77, 100, 53, 72, 77, 16, 8, 36, 41, 58, 59, 29, 46, 79, 81, 66, 8, 35, 60, 52, 2, 82, 2, 36, 79, 66]

    n = len(L)
    for i in range(n-1):
        flag = False
        for j in range(n-i-1):
            if L[j] > L[j+1]:
                L[j], L[j+1] = L[j+1], L[j]
                flag = True
        if not flag:
            break

    return L


print('Bubble sort function run 1000 times, cost: ', timeit('bubbLe_sort()', 'from __main__ import bubbLe_sort', number=1000), 'seconds.')

# Output:
# Bubble sort function run 1000 times, cost:  1.857605113 seconds.

乍一看跟算法2性能一样,但是假如传入已经按 "升序" 排列好的列表,此时算法3是最优时间复杂度O(n)

from timeit import timeit


def bubbLe_sort2():
    L = list(range(1, 101))  # 1...100的顺序整数列表
    n = len(L)
    for i in range(n-1):
        for j in range(n-i-1):
            if L[j] > L[j+1]:
                L[j], L[j+1] = L[j+1], L[j]

    return L


def bubbLe_sort3():
    L = list(range(1, 101))  # 1...100的顺序整数列表,此时是最优时间复杂度O(n)
    n = len(L)
    for i in range(n-1):
        flag = False
        for j in range(n-i-1):
            if L[j] > L[j+1]:
                L[j], L[j+1] = L[j+1], L[j]
                flag = True
        if not flag:
            break

    return L


print('Bubble sort function 02 run 1000 times, cost: ', timeit('bubbLe_sort2()', 'from __main__ import bubbLe_sort2', number=1000), 'seconds.')
print('Bubble sort function 03 run 1000 times, cost: ', timeit('bubbLe_sort3()', 'from __main__ import bubbLe_sort3', number=1000), 'seconds.')

# Output:
# Bubble sort function 02 run 1000 times, cost:  1.051797686 seconds.
# Bubble sort function 03 run 1000 times, cost:  0.029411535000000155 seconds.

3. 性能

3.1 时间复杂度

  • 最优时间复杂度: 需要O(n)次比较(comparisons),和O(1)次交换(swaps)。比如传入已经按 "升序" 排好序的列表时,章节2.3的代码首先会进行第1次外层循环,内层循环n-1次后,会结束算法,所以为O(n)
  • 最坏时间复杂度: 需要O(n^2)次比较,和O(n^2)次交换。比如传入已经按 "降序" 排好序的列表,却需要按 "升序" 去排列它
  • 平均时间复杂度: 需要O(n^2)次比较,和O(n^2)次交换

3.2 空间复杂度

它是in-place comparison sort,总的空间复杂度(total)为O(n);还需要一个临时变量来交换元素位置,辅助空间复杂度(auxiliary)为O(1)

3.3 稳定性

冒泡算法是比较相邻两元素的大小,如果他们的顺序错误就把他们交换过来,它是稳定的排序算法,比如传入 [2, 2, 2, 1],按 "升序" 排序后,三个2总是维持原来的相对次序 [1, 2, 2, 2]

4. 算法的优劣势

4.1 优势

  • 当传入的待排序序列的元素个数很少时,性能好
  • 算法用编程语言易于实现
  • 占用内存空间少(in-place comparison sort
  • 稳定排序

4.2 劣势

时间复杂度为O(n^2),当序列元素很多时,性能非常差

代码已上传到 https://github.com/wangy8961/python3-algorithms ,欢迎star

未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3排序算法01 - 冒泡排序

分享

作者

作者头像

Madman

如果博文内容有误或其它任何问题,欢迎留言评论,我会尽快回复; 或者通过QQ、微信等联系我

0 条评论

暂时还没有评论.

发表评论前请先登录