冒泡排序

简述

假设现在有一个含有 n 个元素的待排序数组，冒泡排序的整个排序过程大致如下

1. 从集合第一个元素开始，每两个相邻元素进行大小比较，令数值较大的元素向后移动，即交换两个元素的位置，不断对比直至数组的末尾。经过第一趟对比，找到整个集合中最大的元素，并将其移动到集合最后一个位置。
2. 继续进行第二趟排序，仍然从集合的第一个元素出发，相邻元素比较大小，比较至集合中倒数第二个元素为止，找到集合中第二大的元素，并使其处于集合的倒数第二位。
3. 每趟结束后都会有一个元素找到自己最终在集合中的位置，不断从第一个元素开始进行 $n-1$ 趟上述过程，即可完成所有元素的排序，实现将集合从小到大排序。

示例代码

Python

from random import randint
from typing import List

def random_list(length: int = 10, start: int = 10, end: int = 100) -> List[int]:
    """生成指定长度的随机整数列表

    Args:
        length (int, optional): 随机数列表长度. Defaults to 10.
        start (int, optional): 范围最小值. Defaults to 10.
        end (int, optional): 范围最大值. Defaults to 100.

    Returns:
        List[int]: 随机数列表
    """
    return [randint(start, end) for _ in range(length)]

def bubble_sort(nums: List[int]) -> List[int]:
    """冒泡排序法"""
    if len(nums) <= 1:
        return nums
    for i in range(len(nums) - 1):
        for j in range(len(nums) - 1 - i):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums

if __name__ == "__main__":
    origin_nums = random_list(100*100)
    print(origin_nums)
    print(bubble_sort(origin_nums))