冒泡排序🌟🌟🌟🌟🌟
这篇文章主要讲解冒泡算法，冒泡排序是一种比较简单的排序算法。虽然在排序算法中不是最优的选择，但是了解这个算法有助于理解更高级的排序算法。
冒泡排序的原理很简单：算法的核心是在排序的过程中将数组分成有序和无序的两部分，并在排序的过程中不断的让无序的部分变得有序。
怎么变有序的？我们每次从第一个元素开始，依次比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置（升序）。并重复这个过程。
冒泡算法流程分析
我们通过一个对有 n 个元素的数组进行冒泡排序的具体例子，来演示这个过程。
排序之前
8 2 4 6 9 6
排序之前整个数组从 [0, n - 1] 这个范围都是无序的。
第一轮冒泡
我们从第一个元素开始，依次比较相邻的两个元素，让更大的元素往后冒泡。
第一步：比较 8 和 2，8 > 2，则进行交换，结果：
2 8 4 6 9 6
第二步：比较 8 和 4，8 > 4，则进行交换，结果：
2 4 8 6 9 6
第三步：比较 8 和 6，8 > 6，则进行交换，结果：
2 4 6 8 9 6
第四步：比较 8 和 9，8 < 9，不进行交换，结果不变：
2 4 6 8 9 6
第五步：比较 9 和 6，9 > 6，则进行交换，结果：
2 4 6 8 6 9
经过第一轮冒泡之后，最大的元素就“冒泡”到了数组的最后一个位置。
此时，数组从 [0, n - 2] 这个范围是无序的，从 [n - 1, n - 1] 这个范围是有序的。
接下来，我们只需要对 [0, n - 2] 这个范围重复上面的操作进行排序。
第二轮冒泡
我们依然从第一个元素开始，依次比较相邻的两个元素，让更大的元素往后冒泡。
接下来希望大家自己按照这个比较的方法，自己推演体会这个过程。
第二轮冒泡结果：
2 4 6 6 8 9
经过第二轮冒泡之后，倒数第二大的元素就“冒泡”到了数组的倒数第二个位置。
此时，数组从 [0, n - 3] 这个范围是无序的，从 [n - 3, n - 1] 这个范围是有序的。
接下来，我们只需要对 [0, n - 3] 这个范围重复上面的操作进行排序。
继续冒泡
依次类推，我们可以顺利推出下面几次冒泡的结果，并在最后得到有序的数组。
第三轮冒泡结果
2 4 6 6 8 9
第四轮冒泡结果
2 4 6 6 8 9
第五轮冒泡结果
2 4 6 6 8 9
代码实现
public void bubbleSort(int[] nums) {
for (int i = nums.length; i > 0; i--) {
for (int j = 0; j < i - 1; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
}
}
}
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
时间复杂度
了解过时间复杂度的人可以很明显的看出来冒泡排序的时间复杂度是 ${O(n^2)}$。
但是细心的人也会发现在上面所举的例子中，其实在第三轮冒泡排序之后，我们的数组已经是有序的了，但还是会继续对数组剩下的无序部分进行冒泡。
因为我们对于数组无序部分的情况是未知的，所以只能继续这个冒泡的循环，保证把这未知的部分也变成有序的。
所以冒泡排序可优化的地方在于，当数组已经有序的时候，停止冒泡的流程。
优化的方式也很简单，如果我们在上一轮冒泡的过程中，数组元素的位置没有发生交换，就证明数组已经是有序的，可以退出剩下的冒泡流程。
实现方式呢，是通过一个变量来进行标记的，实现方式也比较简单。
public void bubbleSort(int[] nums) {
for (int i = nums.length; i > 0; i--) {
boolean flag = false;
for (int j = 0; j < i - 1; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
flag = true;
}
}
if (flag == false) {
break;
}
}
}
通过这个优化，可以发现，如果数组大部分是有序的，那么冒泡排序的在最好的情况下的时间复杂度是 ${O(n)}$，那么在这种情况下，使用冒泡排序也是一种蛮不错的选择。
空间复杂度
冒泡排序属于典型的原地排序算法，空间复杂度为 ${O(1)}$，因为只需要常数级别的额外空间来存储临时变量。
稳定性
冒泡排序是一种稳定的排序算法。稳定性指的是相同元素的相对位置在排序前后不发生变化。在冒泡排序中，当相邻两个元素相等时，是不进行交换的，因此相同元素的相对位置不会改变，从而保持了稳定性。
写在最后
总的来说，冒泡排序虽然简单，但是了解这个算法可以帮助我们更好地理解排序算法的原理和思想，同时也可以作为基础知识为学习更高级的
排序算法打下基础。希望通过这篇介绍，读者能对冒泡排序有一个初步的了解，为日后的学习和实践打下基础。