一、排序：时间复杂度O(n*n)

1.1 冒泡排序

class BubbleSort:
    """
    冒泡排序
    时间复杂度：最坏 O(n*n)、平均 O(n*n)、最优 O(n)
    空间复杂度：O(1)
    简介：
        1 循环一次列表，对每相邻两个元素做比较，决定是否交换
        2 一次循环后，有序区个数+1，无序区个数-1
        3 再对无序区重复步骤1
    """

    def sort(self, li):
        """
        冒泡排序
        :param li:
        :return:
        """
        n = len(li)
        for n_ in range(n - 1):
            change_flag = False  # 判断原始数据是否是有序的标志
            for i in range(n - n_ - 1):
                if li[i] > li[i + 1]:  # 相邻元素做比较
                    li[i], li[i + 1] = li[i + 1], li[i]
                    change_flag = True
            if not change_flag:  # 最优时间复杂度O(n)
                break
        return li
      

1.2 选择排序

class SelectSort:
    """
    选择排序
    时间复杂度：最坏 O(n*n)、平均 O(n*n)、最优 O(n*n)
    空间复杂度：O(1)
    简介：
        1 设列表第一个元素为有序区，后面元素为无序区
        2 遍历一遍无序区，找到无序区中比有序区最后一个元素更小的元素，并交换
        3 对无序区重复步骤1，有序区个数+1，无序区个数-1
    """

    def sort(self, li):
        """
        选择排序
        :param li:
        :return:
        """
        n = len(li)
        for n_ in range(n - 1):
            min_loc = n_
            for i in range(n_ + 1, n):
                if li[i] < li[min_loc]:  # 找到无序区中比有序区最后一个元素更小的元素
                    min_loc = i
            li[n_], li[min_loc] = li[min_loc], li[n_]  # 元素交换
        return li
      

1.3 插入排序

class InsertSort:
    """
    插入排序
    时间复杂度：最坏 O(n*n)、平均 O(n*n)、最优 O(n*n)
    空间复杂度：O(1)
    简介：
        1 设列表第一个元素为有序区，后面元素为无序区
        2 从无序区（右）选择一个元素，插入当前有序区（左）的正确位置
        3 重复步骤2，有序区个数+1，无序区个数-1
    """

    def sort(self, li):
        """
        插入排序实现方式1
        :param li:
        :return:
        """
        n = len(li)
        for right in range(1, n):
            curr = li[right]
            for left in range(right - 1, -1, -1):
                if li[left] > curr:  # curr和有序区元素逐个比较
                    li[left + 1] = li[left]
                else:  # 直到找到正确的位置，退出循环
                    li[left + 1] = curr
                    break
            else:  # curr比有序区所有元素都小
                li[right % 1] = curr
        return li

    def sort_2(self, li):
        """
        插入排序实现方式2
        :param li:
        :return:
        """
        n = len(li)
        for right in range(1, n):
            curr = li[right]
            left = right - 1
            while left >= 0 and li[left] > curr:  # curr和有序区元素逐个比较，直到找到正确的位置，退出循环
                li[left + 1] = li[left]
                left -= 1
            li[left + 1] = curr  # 补充空位
        return li