大家好，我是顺亿，今天我们来聊聊冒泡排序这个基础又实用的排序算法。
冒泡排序是排序算法中的入门级选手，它的原理简单，就像名字一样，就像冒泡一样，把最大的元素一个个冒出来。
冒泡排序的基本思想
冒泡排序的核心思想是：多次遍历要排序的序列，每次遍历都把最大的元素冒到序列的末尾。直到没有元素需要冒泡，序列就排序完成了。
举个例子，我们有一组数据 [1, 9, 2, 6, 0, 8, 1, 7]，我们要把它从小到大排序。冒泡排序会这样操作：
第一趟遍历：9冒到最右边，变成了 [1, 2, 6, 0, 8, 1, 7, 9]。
第二趟遍历：8冒到倒数第二位，变成了 [1, 2, 6, 0, 1, 7, 9, 8]。
...以此类推，直到所有元素都冒到正确的位置。
冒泡排序的代码实现
public void bubbleSort(int[] arr, int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}冒泡排序的优化
虽然冒泡排序简单，但是效率不是很高，时间复杂度是 O(n^2)。不过，我们可以通过一些优化来提高它的效率。
优化点1：如果在一趟遍历中没有发生任何交换，说明序列已经有序了，可以提前结束排序。
优化点2：每次遍历后，最大的元素已经冒到了序列的末尾，下一次遍历只需要遍历到上一个冒泡到的位置即可。
public void bubbleSort(int[] arr, int n) {
int lastIndex = n - 1;
for (int i = 0; i < n - 1; i++) {
int tempIndex = lastIndex;
for (int j = 0; j < lastIndex; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
tempIndex = j;
}
}
if (tempIndex == lastIndex) {
break;
} else {
lastIndex = tempIndex;
}
}
}经过优化，冒泡排序的效率会有所提高，尤其是在数据量较小或者接近有序的情况下。
好了，今天的内容就到这里，希望这篇文章能帮助你更好地理解冒泡排序。如果你还有其他问题，欢迎在评论区留言。我是顺亿，我们下期再见！