def bubble_sort1(nums: list[int]):
    if len(nums) <= 1:
        return nums

    # 外层循环表示是在排序第i个最大值
    for i in range(len(nums)):
        # 减 1 防止索引越界
        # 减 i 表示已经将 i 个最大值排序到了末尾，无需再比较
        for j in range(len(nums) - i - 1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]


"""
冒泡排序优化1：使用一个标志位，对列表中已排序的部分不再排序
"""


def bubble_sort2(nums: list[int]):
    compare: bool = True
    length = len(nums)

    while length > 0 and compare:
        compare = False
        for i in range(length):
            if nums[i] > nums[i + 1]:
                nums[i], nums[i + 1] = nums[i + 1], nums[i]
                # 数据无序，后续部分仍需比较
                compare = True
        # 每次比较，最大的数都会被放到末尾，因此减1，减少一次对比
        length -= 1


"""
冒泡排序优化2：鸡尾酒排序，双向排序
"""


def bubble_sort3(nums: list[int]):
    length = len(nums)
    if length <= 1:
        return nums

    bubble = True
    for i in range(length >> 1):
        if bubble:
            bubble = False

            # 从左到右冒泡
            for j in range(i, length - i - 1):
                if nums[j] > nums[j + 1]:
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]
                    bubble = True

            for j in range(length - i - 1, i, -1):
                if nums[j] < nums[j - 1]:
                    nums[j], nums[j - 1] = nums[j - 1], nums[j]
                    bubble = True

        else:
            break


"""
冒泡排序优化3：梳排序，在冒泡排序中，只会比较数组中相邻的项，比较间距为 1

梳排序中，开始比较间距设定为数组长度，并在循环中以固定的比率递减，通常递减率为 1.3，
该数字是原作者通过实验得到的最有效递减率
"""


def comb_sort(nums: list[int]):
    if len(nums) <= 1:
        return nums

    gap = len(nums)

    # 大致排序，数据基本有序
    while gap > 0:
        gap = int(gap * 0.8)
        i = gap
        while i < len(nums):
            if nums[i - gap] > nums[i]:
                nums[i], nums[i - gap] = nums[i - gap], nums[i]
            i += 1

    # 细致调节无序部分
    exchange = True
    while exchange:
        exchange = False
        i = 0
        while i < len(nums) - 1:
            if nums[i] > nums[i + 1]:
                nums[i], nums[i + 1] = nums[i + 1], nums[i]
                exchange = True

            i += 1