冒泡排序（Bubble Sort）

一、基本思想

Bubble sort is the simplest of all sorting algorithms.它是一种基于比较排序的算法,The main sorting idea of ​​this algorithm is to compare each pair of adjacent elements,如果它们的顺序不对,就交换它们,Eventually all elements reach an ordered state.

二、实现逻辑

首先有一个数组,It stores the elements to be sorted.If you need to arrange larger elements to the back,Arrange small elements to the front,Then you need to start the following comparison operations from beginning to end：

1. Compares two adjacent elements starting from the head,If the element at the head is larger than the one at the back,就交换两个元素的位置;
2. Do this comparison for each adjacent element in the future、交换操作,This way to the end of the array,The first element becomes the smallest element;
3. Except for sorted elements,Start over from the head again1、2步的操作;
4. 继续对越来越少的数据进行比较、交换操作,直到没有可比较的数据为止,排序完成.

外循环遍历,The inner loop compares the elements.

三、时间复杂度的分析

最坏情况下,The sequence is reversed,需要比较的次数为 $n(n-1)/2$（$n$ At most data elements exist$\frac{n(n-1)}{2}$ 对逆序）,The corresponding time complexity is ：$O(n^2)$.

最优情况下,The sequence is already sorted,只需要比较 $n-1$ to exit the outer loop,即时间复杂度为 $\Omega (n^2)$.

对于 $n$ common to all elements $n!$ different sequences,On average each sequence has to exist $\frac{n(n-1)}{4}$ 对逆序,So the average time complexity of bubble sort is $\Theta (n^2)$ .

四、Analysis of space time complexity

Since comparing swap elements does not open up additional memory space,Therefore, the space complexity is ：$O(1)$.

五、算法实现

普通版本

def bubble_sort(array: List) -> None:
	''' 支持数值型数据,如整型与浮点型混合;支持全为字符串类型的数据;不支持字符串型与数值型混合. '''
    for i in range(len(array) - 1): # loop to access each array element
        for j in range(len(array) - i - 1): # loop to compare array elements
        # compare two adjacent elements and change > to < to sort in descending order
            if array[j] > array[j + 1]:
                # swapping elements if elements are not in the intended order
                array[j], array[j + 1] = array[j + 1], array[j]

添加"旗帜"

def bubble_sort(array: List) -> None:
	''' 支持数值型数据,如整型与浮点型混合;支持全为字符串类型的数据;不支持字符串型与数值型混合. '''
    for i in range(len(array) - 1):
        flag = False # 旗帜
        for j in range(len(array) - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
                flag = True
        if not flag:
            break

双向排序

def bubble_sort(array: List) -> None:
	''' 支持数值型数据,如整型与浮点型混合;支持全为字符串类型的数据;不支持字符串型与数值型混合. '''
    for i in range(len(array) - 1):
        flag = False
        for j in range(len(array) - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
                flag = True
        if flag: # 反向排序
            flag = False
            for j in range(len(array) - i - 2, 0, -1):  
                if array[j - 1] > array[j]:
                    array[j], array[j - 1] = array[j - 1], array[j]
                    flag = True
        if not flag:
            break