冒泡排序

概念

冒泡排序是一种简单的排序算法，它重复地遍历待排序的元素，每次遍历时依次比较相邻的两个元素，如果它们的顺序错误（例如，对于升序排序，前一个元素大于后一个元素），则交换它们的位置。通过一轮完整的遍历，可以确保最大（或最小）的元素被移动到了正确的位置。重复这个过程，每次比较的元素范围都会缩小，直到所有元素都排好序为止。

冒泡排序的算法步骤如下：

从第一个元素开始，依次比较相邻的两个元素。
如果前一个元素大于后一个元素，则交换它们的位置。
继续遍历下一对相邻元素，重复步骤2。
重复以上步骤，直到没有任何一对元素需要交换为止。

冒泡排序的特点是简单易懂，但效率较低，特别是对于大型数据集。其时间复杂度为 O(n²)，其中n是待排序元素的数量，因此在实践中通常不适用于大规模数据的排序。

优缺点

冒泡排序是一种简单但效率较低的排序算法，其优缺点如下：

优点：

实现简单：冒泡排序的实现非常简单，易于理解和实现。
原地排序：冒泡排序只需要一个额外的空间用于交换元素，因此是一种原地排序算法，不需要额外的存储空间。
稳定性：冒泡排序是一种稳定的排序算法，相同元素的相对位置不会改变。

缺点：

低效率：冒泡排序的时间复杂度为 O(n²)，其中n是待排序数组的长度。在大规模数据集上，效率较低，特别是相比于其他高效的排序算法，如快速排序、归并排序等。
不适合大规模数据：由于其时间复杂度较高，冒泡排序不适用于大规模数据的排序，其性能表现往往不如其他更高效的排序算法。
稳定性代价：虽然冒泡排序是稳定的，但在进行元素交换时可能会破坏相同元素之间的原始顺序，因此需要额外的操作来保持稳定性。

代码实现

type Number interface {
	int | int8 | int16 | int32 | int64 |
		uint | uint8 | uint16 | uint32 | uint64 |
		float32 | float64
}

func BubbleSort[T Number](arr []T) []T {
	n := len(arr)
	for i := 0; i < n-1; i++ {
		for j := 0; j < n-i-1; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j] // 交换元素
			}
		}
	}
	return arr
}

我们可以大致推导一下冒泡的过程：

type Number interface {
	int | int8 | int16 | int32 | int64 |
		uint | uint8 | uint16 | uint32 | uint64 |
		float32 | float64
}

// 假设数组为 [2,4,3,1]
func BubbleSortStep[T Number](arr []T) {
	n := len(arr) // n = 4

	// 当前数组：[2,4,3,1]
	// 第 1 轮，需要比较 n-1 次，即需要比较 3 次，并在比较中和较小的数交换位置
	// 第一次比较：2 和 4 比较，不需要交换位置，结果为 [2,4,3,1]
	// 第二次比较：4 和 3 比较，4 > 3 需要交换位置，结果为 [2,3,4,1]
	// 第三次比较：4 和 1 比较，4 > 1 需要交换位置，结果为 [2,3,1,4]
	// 至此，第一轮比较完成，最大数字 4 移动到最后
	for i := 0; i < n-1; i++ {
		if arr[i] > arr[i+1] {
			arr[i], arr[i+1] = arr[i+1], arr[i]
		}
	}

	// 当前数组：[2,3,1,4]
	// 第 2 轮，需要比较 n-2 次，即需要比较 2 次，因为最大数字已经移动到最后，不再需要参加比较
	// 第一次比较：2 和 3 比较，不需要交换位置，结果为 [2,3,1,4]
	// 第二次比较：3 和 1 比较，3 > 1 需要交换位置，结果为 [2,1,3,4]
	// 至此，第一轮比较完成，倒数第二大数字 3 移动到最后
	for i := 0; i < n-2; i++ {
		if arr[i] > arr[i+1] {
			arr[i], arr[i+1] = arr[i+1], arr[i]
		}
	}

	// 第 3 轮，需要比较 n-3 次，过程同上
	for i := 0; i < n-3; i++ {
		if arr[i] > arr[i+1] {
			arr[i], arr[i+1] = arr[i+1], arr[i]
		}
	}

	// 第 n-1 轮，需要比较 n-(n-1)=1 次
	for i := 0; i < n-3; i++ {
		if arr[i] > arr[i+1] {
			arr[i], arr[i+1] = arr[i+1], arr[i]
		}
	}

	// 发现规律：第 m 轮，需要比较 n-m 次
	var m int
	for i := 0; i < n-m; i++ {
		if arr[i] > arr[i+1] {
			arr[i], arr[i+1] = arr[i+1], arr[i]
		}
	}

	// 因为是相邻的数字两两比较，所以总共需要比较 n-1 轮，
	// 且每轮比较的次数减 1，因为每轮比较后会冒泡最大的数字到最右侧不再参与比较
	for j := 0; j < n-1; j++ { // 每次比较相邻两个数，需要比较 n-1 轮
		for i := 0; i < n-(j+1); i++ { // 每轮比较后，最大的数会冒泡到最右侧，故下一轮比较就会少 1 次
			if arr[i] > arr[i+1] { // 相邻元素比较
				arr[i], arr[i+1] = arr[i+1], arr[i] // 交换元素
			}
		}
	}

}

总结

冒泡排序：依次比较和交换相邻的两个元素，将较大的元素逐个冒泡到尾部。

复杂度：

平均时间复杂度：O(n²)
最坏时间复杂度：O(n²)
最优时间复杂度：O(n)
空间复杂度：O(n)

参考：冒泡排序-维基百科

冒泡排序 ​

概念 ​

优缺点 ​

代码实现 ​

总结 ​

冒泡排序

概念

优缺点

代码实现

总结