冒泡排序(python实现)

冒泡排序

冒泡排序（Bubble Sort）是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序步骤

1. 算法步骤

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

• 针对所有的元素重复以上的步骤，除了最后一个。

• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

# 冒泡排序
def bubble_sort(array):
    '''
    原始冒泡排序：从小到大
    '''
    compare_count = 0
    for i in range(len(array) - 1):  # n个数，只需要n-1次冒泡
        for j in range(len(array) - i - 1):
            compare_count += 1
            if array[j] > array[j+1]:
                array[j], array[j + 1] = array[j + 1], array[j]
    print("bubble_sort circle num:", compare_count)
    return array

• 冒泡排序n个数，只需要n-1轮冒泡即可。
• 冒泡排序第i轮冒泡完毕后，肯定会将索引为n-i-1的位置排序好，因此只需要循环到j= n-i-2即可
• 没有进行交换，说明数据已经有序
• 最后一个被交换的元素下标即为无序和有序的边界

冒泡排序优化

优化一：

冒泡排序优化：本次循环没有冒泡（交换），说明数据已经有序，可以直接退出

# -*- coding:utf-8 -*-

def bubble_sort2(array):
    '''
    冒泡排序优化：本次循环没有冒泡（交换），说明数据已经有序，可以直接退出
    '''
    compare_count = 0
    for i in range(len(array) - 1):
        swapped_flag = False
        for j in range(len(array) - i - 1):
            compare_count += 1
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j + 1], array[j]
                swapped_flag = True
        if not swapped_flag:
            break
    print('bubble_sort2 circle num:', compare_count)
    return array

优化2

bubble_sort2的基础上再优化。
优化思路：在排序的过程中，数据可以从中间分为两段，一段是无序状态，另一段是有序状态。每一次循环的过程中，记录最后一个交换元素的索引，它便是有序和无序状态的边界下一次仅循环到边界即可，从而减少循环次数，达到优化。

# 冒泡排序优化：本次循环没有冒泡（交换），说明数据已经有序，可以直接退出
def bubble_sort3(array):
    '''
     bubble_sort2的基础上再优化。
    优化思路：在排序的过程中，数据可以从中间分为两段，一段是无序状态，另一段是有序状态。
    每一次循环的过程中，记录最后一个交换元素的索引，它便是有序和无序状态的边界
    下一次仅循环到边界即可，从而减少循环次数，达到优化。
    '''
    compare_count = 0
    last_swapped_index = 0
    border = len(array) - 1  # 有序和无序的分界线

    for i in range(len(array) - 1):
        swapped_flag = False
        for j in range(border):
            compare_count += 1
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j + 1], array[j]
                swapped_flag = True
                last_swapped_index = j
        if not swapped_flag:
            break
        border = last_swapped_index
    print('bubble_sort3 circle num:', compare_count)
    return array

3. 循环次数比较

if __name__ == '__main__':
    array = [2, 4, 1, 3, 5, 8, 7, 8, 4, 9]
    array2 = [] + array
    array3 = [] + array
    print('-'*20)
    print bubble_sort(array)
    print('-'*20)
    print bubble_sort2(array2)
    print('-'*20)
    print bubble_sort3(array3)

输出：

--------------------
('bubble_sort circle num:', 45)
[1, 2, 3, 4, 4, 5, 7, 8, 8, 9]
--------------------
('bubble_sort2 circle num:', 35)
[1, 2, 3, 4, 4, 5, 7, 8, 8, 9]
--------------------
('bubble_sort3 circle num:', 31)
[1, 2, 3, 4, 4, 5, 7, 8, 8, 9]

冒泡排序复杂度

1.时间复杂度：
最小时间复杂度：最好的情况是数据一开始就是有序的，因此一次冒泡即可完成
最大时间复杂度：最坏的情况就是数据一开始就是倒序的，因此进行 n-1 次冒泡

• 平均时间复杂度：O(n^2)
• 最大时间复杂度：O(n^2)
• 最小时间复杂度：O(n)

2. 空间复杂度：O(1)
3. 稳定性：稳定

参考：Python-排序-冒泡排序-优化