冒泡排序

基本概念

冒泡排序（Bubble Sort）基本思想：
通过相邻元素的比较与交换，将较大的元素逐步「冒泡」到数组末尾，较小的元素自然「下沉」到数组开头。

算法步骤

对于长度为 n 的数组，冒泡排序的步骤如下：

第1趟冒泡：对前n个元素依次比较相邻元素，将较大的元素向右交换，最终使最大值移动到数组末尾（第n个位置）。
1. 比较第1个和第2个元素，如果前者大于后者则交换。
2. 比较第 2 个和第 3 个元素，如果前者大于后者则交换。
3. 以此类推，直到比较第 n−1 个和第 n 个元素。
4. 完成后，最大元素已位于末尾。
第 2 趟冒泡：对前 n−1 个元素重复上述过程，将次大值移动到倒数第二个位置（第 n−1 个位置）。
1. 比较第1个和第 2 个元素，如果前者大于后者则交换。
2. 比较第 2 个和第 3 个元素，如果前者大于后者则交换。
3. 以此类推，直到比较第 n−2 个和第 n−1 个元素。
4. 完成后，次大元素已位于倒数第二位。
持续进行上述冒泡过程，每一趟比较的元素个数递减，直到某一趟未发生任何交换，说明数组已完全有序，排序结束。

内部实现：

class Solution:
	def bubbleSort(self,nums:[int])->int:
		n=len(nums)
		for i in range(n-1):
			swapped=False
			for j in range(n-1):
				if nums[j]>nums[j+1]:
					nums[j],nums[j+1]=hums[j+1],nums[j]
					swapped=True
			if not swapped:
				break
		return nums
	def sortArray(self,nums:[int])->[int]:
		return self.bubbleSort(nums)

复杂度分析：

指标	复杂度	说明
最佳时间复杂度	$O(n)$	数组已有序，只需一趟遍历
最坏时间复杂度	$O(n^2)$	数组逆序，需要 nn 趟遍历
平均时间复杂度	$O(n^2)$	一般情况下的复杂度
空间复杂度	$O(1)$	原地排序，只使用常数空间
稳定性	稳定	相等元素相对位置不变

数据量较小（n<50）
数据基本有序
冒泡排序是最简单的排序算法之一，通过相邻元素比较交换实现排序。虽然实现简单，但效率较低。
优点：实现简单，稳定排序，空间复杂度低。
缺点：时间复杂度高，交换次数多。

冒泡排序

基本概念

算法步骤

内部实现：

复杂度分析：

应用场景：