一、冒泡排序

比较简单的排序算法，适合小规模数据集，效率较低。
依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。
每进行一趟排序，就会少比较一个数

python代码（非递归）：

from typing import List

class Solution:
    def BubbleSort(self, seq: List[int]) -> List[int]:
        for i in range(len(seq)):     #外层循环控制内层循环的长度
            for j in range(0, len(seq) - i):
                try:
                    if seq[j] > seq[j+1]:       #如果前一个元素值大于后一个元素值，交换元素
                        seq[j], seq[j+1] = seq[j+1], seq[j]
                except:
                    pass
        return seq           
a = Solution()
ans = a.BubbleSort([3, 4, 2, 1, 5, 1]) 
print(ans)

python代码（递归）：

from typing import List

class Solution:
    def BubbleSort(self, seq: List[int], bblen: int) -> List[int]:

        for j in range(0, bblen):
            print(bblen)
            try:
                if seq[j] > seq[j+1]:
                      seq[j], seq[j+1] = seq[j+1], seq[j]
            except:
                pass
        bblen -= 1   
        if bblen <= 0: return seq 
        self.BubbleSort( seq, bblen)
        return seq  
         
a = Solution()
bblist = [3, 4, 2, 1, 5, 1]
ans = a.BubbleSort(bblist, len(bblist)) 
print(ans)

时间复杂度分析

最好的情况，也就是要排序的表本身就是有序的，那么我们比较次数，可以判断出就是n-1次的比较，没有数据交换，此时时间复杂度为O(n)
当最坏的情况，即待排序是逆序的情况，需要比较 $\sum_{i=2}^{n}i-1=1+2+3+....+(n-1)=\frac{n(n-1)}{2}$ 次，此时时间复杂度为 $o(n^{2})$ 。