冒泡排序是最简单的排序算法。冒泡排序基于这样的思想:如果发现顺序错误，则对每个相邻元素进行比较和交换。
示例:
要理解冒泡排序，让我们考虑一个未排序的数组 [1, 23, 10, -2] 并讨论按升序对数组进行排序所采取的每个步骤。在每次传递中，都会检查两个相邻元素，如果发现顺序错误则进行交换。
第一次通过: (1) 和 (23) 进行比较并发现正确的顺序（在本例中为升序）。之后比较 (23) 和 (10)，因为 (23>10)，因此这些数字被交换。然后比较并交换 (23) 和 (-2)。
第二遍: 比较(1)和(10)并发现顺序正确。然后比较 (10) 和 (-2)，因为 (10>-2)，因此这些数字被交换。之后，比较(10)和(23)并按正确的顺序找到。
第三遍 : (1) 和 (-2) 进行比较，因为 (1>-2)，因此这些数字被交换。之后检查 (1,10) 和 (10,23) 并按正确顺序找到。
冒泡排序的实现
public class MyClass {
// 冒泡排序函数
static void bubblesort(int Array[]) {
int n = Array.length;
int temp;
for(int i=0; i<n; i++) {
for(int j=0; j<n-i-1; j++) {
if(Array[j]>Array[j+1]) {
temp = Array[j];
Array[j] = Array[j+1];
Array[j+1] = temp;
}
}
}
}
//打印数组的函数
static void PrintArray(int Array[]) {
int n = Array.length;
for (int i=0; i<n; i++)
System.out.print(Array[i] + " ");
System.out.println();
}
//测试代码
public static void main(String[] args) {
int[] MyArray = {1, 10, 23, 50, 4, 9, -4};
System.out.println("原始数组");
PrintArray(MyArray);
bubblesort(MyArray);
System.out.println("\n排序数组");
PrintArray(MyArray);
}
} 上面的代码将给出以下输出:
原始数组
1 10 23 50 4 9 -4
排序数组
-4 1 4 9 10 23 50 时间复杂度:
在所有情况下，即使整个数组已排序，冒泡排序的时间复杂度也是θ(N²)，因为整个数组的每个元素都需要迭代，它包含两个嵌套循环。