排序-冒泡排序
冒泡排序(Bubble Sort)是一种简单直观的排序算法。它重复地遍历要排序的数组,一次比较两个元素,如果它们的顺序错误就进行交换。遍历数组的工作是重复进行的,直到没有再需要交换,也就是说数组已经排序完成。
下面将详细讲解冒泡排序的原理、步骤、时间复杂度、空间复杂度、优缺点以及优化方法,并提供示例代码来帮助理解。
一、排序原理
冒泡排序的核心思想是通过多次比较和交换,使较大的元素逐渐“冒泡”到数组的末端。具体过程如下:
- 比较相邻的元素:从数组的起始位置开始,依次比较每对相邻的元素。
- 交换顺序:如果前一个元素比后一个元素大(或根据需要的排序顺序),则交换它们的位置。
- 重复遍历:完成一次遍历后,最后的元素是该数组中最大的元素(对于升序排序)。
- 迭代进行:对除最后一个元素外的剩余部分重复上述过程,直到整个数组有序。
二、步骤详解
以升序排序为例,具体步骤如下:
-
第一轮遍历:
- 从数组的第一个元素开始,依次比较相邻的两个元素。
- 如果前一个元素大于后一个元素,则交换它们的位置。
- 经过第一轮遍历后,最大的元素被“冒泡”到数组的末端。
-
第二轮遍历:
- 对前
n-1
个元素重复上述步骤,忽略已经排好序的最后一个元素。 - 经过第二轮遍历后,第二大的元素被排到倒数第二的位置。
- 对前
-
继续迭代:
- 每一轮遍历都将下一个最大元素“冒泡”到合适的位置。
- 重复此过程,直到整个数组有序。
示例
假设有一个数组 [5, 3, 8, 4, 2]
,进行升序排序:
-
第一轮遍历:
- 比较
5
和3
,因为5 > 3
,交换得到[3, 5, 8, 4, 2]
。 - 比较
5
和8
,不交换,数组保持[3, 5, 8, 4, 2]
。 - 比较
8
和4
,因为8 > 4
,交换得到[3, 5, 4, 8, 2]
。 - 比较
8
和2
,因为8 > 2
,交换得到[3, 5, 4, 2, 8]
。
- 第一轮结束,最大元素
8
已经在末端。
- 比较
-
第二轮遍历:
- 比较
3
和5
,不交换,数组保持[3, 5, 4, 2, 8]
。 - 比较
5
和4
,因为5 > 4
,交换得到[3, 4, 5, 2, 8]
。 - 比较
5
和2
,因为5 > 2
,交换得到[3, 4, 2, 5, 8]
。
- 第二轮结束,第二大元素
5
已经在倒数第二的位置。
- 比较
-
第三轮遍历:
- 比较
3
和4
,不交换,数组保持[3, 4, 2, 5, 8]
。 - 比较
4
和2
,因为4 > 2
,交换得到[3, 2, 4, 5, 8]
。
- 第三轮结束,第三大元素
4
已经在倒数第三的位置。
- 比较
-
第四轮遍历:
- 比较
3
和2
,因为3 > 2
,交换得到[2, 3, 4, 5, 8]
。
- 第四轮结束,第四大元素
3
已经在倒数第四的位置。
- 比较
-
最终结果:数组已经按升序排列
[2, 3, 4, 5, 8]
。
三、时间复杂度
-
最优时间复杂度:O(n)
当数组已经有序时,只需要进行一次遍历,无需交换。 -
平均时间复杂度:O(n²)
无论初始状态如何,通常需要进行多次遍历和交换。 -
最坏时间复杂度:O(n²)
当数组完全逆序时,需要进行最多的交换次数。
四、空间复杂度
- 空间复杂度:O(1)
冒泡排序是一种原地排序算法,只需要常数级别的额外空间。
五、稳定性
冒泡排序是一种稳定的排序算法。稳定性指的是相同元素的相对顺序在排序后保持不变。由于冒泡排序只在前一个元素大于后一个元素时才进行交换,因此相同元素不会被改变相对位置。
六、优缺点
优点
- 实现简单:算法逻辑直观,容易编写和理解。
- 稳定性:保持相同元素的相对位置不变。
- 空间效率高:仅需常数级别的额外空间。
缺点
- 时间效率低下:对于大规模数据,冒泡排序效率较低,性能不佳。
- 交换操作频繁:在元素需要移动较远位置时,交换次数较多,影响性能。
七、优化方法
尽管冒泡排序在一般情况下效率较低,但可以通过一些优化措施提高其性能:
1. 提前结束排序
在某一轮遍历中,如果没有发生任何交换,说明数组已经有序,可以提前结束排序,减少不必要的遍历次数。
实现方法:
- 引入一个布尔标志
swapped
,初始为false
。 - 在遍历过程中,如果发生交换,则将
swapped
设为true
。 - 遍历结束后,检查
swapped
是否为true
,如果没有交换则终止排序。
示例代码:
public void optimizedBubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 和 arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// 如果没有发生交换,数组已经有序
if (!swapped) {
break;
}
}
}
2. 记录最后交换的位置
有时数组的后部分可能已经有序,但前面还未完全排序。可以记录每轮遍历中最后一次交换的位置,这样在下一轮遍历时只需遍历到该位置即可,无需遍历整个数组。
实现方法:
- 引入一个变量
lastSwappedIndex
,记录最后一次交换的位置。 - 在下一轮遍历时,只需遍历到
lastSwappedIndex
之前的位置。
示例代码:
public void optimizedBubbleSortWithLastSwap(int[] arr) {
int n = arr.length;
int lastSwappedIndex;
int newn;
newn = n;
do {
lastSwappedIndex = newn;
newn = 0;
for (int i = 0; i < lastSwappedIndex - 1; i++) {
if (arr[i] > arr[i + 1]) {
// 交换 arr[i] 和 arr[i + 1]
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
newn = i + 1;
}
}
} while (newn > 0);
}
八、示例代码
下面提供一个完整的冒泡排序示例,包括优化后的版本:
public class BubbleSortExample {
// 普通冒泡排序
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 和 arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// 优化的冒泡排序(提前结束)
public static void optimizedBubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 和 arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// 如果没有发生交换,数组已经有序
if (!swapped) {
break;
}
}
}
// 优化的冒泡排序(记录最后交换位置)
public static void optimizedBubbleSortWithLastSwap(int[] arr) {
int n = arr.length;
int lastSwappedIndex;
int newn;
newn = n;
do {
lastSwappedIndex = newn;
newn = 0;
for (int i = 0; i < lastSwappedIndex - 1; i++) {
if (arr[i] > arr[i + 1]) {
// 交换 arr[i] 和 arr[i + 1]
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
newn = i + 1;
}
}
} while (newn > 0);
}
// 打印数组
public static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
// 测试冒泡排序
public static void main(String[] args) {
int[] arr1 = {5, 1, 4, 2, 8};
System.out.println("原始数组:");
printArray(arr1);
bubbleSort(arr1);
System.out.println("普通冒泡排序后:");
printArray(arr1);
int[] arr2 = {5, 1, 4, 2, 8};
optimizedBubbleSort(arr2);
System.out.println("优化后的冒泡排序(提前结束)后:");
printArray(arr2);
int[] arr3 = {5, 1, 4, 2, 8};
optimizedBubbleSortWithLastSwap(arr3);
System.out.println("优化后的冒泡排序(记录最后交换位置)后:");
printArray(arr3);
}
}
输出结果:
原始数组:
5 1 4 2 8
普通冒泡排序后:
1 2 4 5 8
优化后的冒泡排序(提前结束)后:
1 2 4 5 8
优化后的冒泡排序(记录最后交换位置)后:
1 2 4 5 8
九、何时使用冒泡排序
虽然冒泡排序实现简单且稳定,但由于其时间复杂度较高,通常仅在以下情况下使用:
- 小规模数据:对于数据量较小的数组,冒泡排序的性能可以接受。
- 教育和学习:冒泡排序是介绍基础排序算法的经典例子,帮助理解排序的基本概念。
- 数据接近有序:如果数据已经基本有序,优化后的冒泡排序可以表现出较好的性能。
然而,在实际应用中,对于大规模数据,通常会选择更高效的排序算法,如快速排序(Quick Sort)、归并排序(Merge Sort)或堆排序(Heap Sort)。
十、总结
冒泡排序是一种简单直观的排序算法,通过重复比较和交换相邻元素,将较大的元素逐步“冒泡”到数组的末端。虽然其时间复杂度为O(n²),在处理大规模数据时效率较低,但由于其实现简单和稳定性,仍在教育和某些特定场景下具有应用价值。通过优化策略,如提前结束和记录最后交换位置,可以在一定程度上提高其性能。
理解冒泡排序有助于掌握排序算法的基本原理,并为学习更复杂的排序算法打下基础。