冒泡排序详解
1. 引言
冒泡排序是一种简单直观的排序算法，其基本思想是通过多次遍历数组，比较相邻元素并交换，使得每一轮遍历后最大的元素都位于数组末尾。
2. 冒泡排序原理
冒泡排序的核心思想是相邻元素两两比较，将较大的元素逐步交换到右侧，通过多轮遍历实现整体排序。
3. 冒泡排序步骤
冒泡排序的具体步骤如下：
- 从第一个元素开始，依次比较相邻元素。
- 如果前一个元素大于后一个元素，则交换它们的位置。
- 继续比较下一组相邻元素，重复步骤2。
- 一轮遍历后，最大的元素将移动到数组末尾。
- 重复以上步骤，每轮遍历确定一个最大元素的位置，直至整个数组有序。
4. 冒泡排序代码示例
4. 1 Python语言实现的冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("排序后的数组:", arr)
|
4. 2 Java语言实现的冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| package org.example;
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int arr[] = {-1, -2, 3, 7, 4, 10};
bubbleSort(arr);
int arr2[] = new int[80000];
for (int i = 0; i < 80000; i++) {
arr2[i] = (int)(Math.random()*8000000);
}
System.out.println("arr2：" + Arrays.toString(arr2));
}
public static void bubbleSort(int[] arr){
boolean flag = false;
System.out.println("初始数组序列：" + Arrays.toString(arr));
int temp = 0;
for (int j = 0; j < arr.length - 1; j++) {
for (int i = 0; i < arr.length - (j + 1); i++) {
if (arr[i] > arr[i + 1]) {
flag = true;
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
if (!flag) {
break;
} else {
flag = false;
}
System.out.printf("第%d躺排序：", j + 1);
System.out.printf(Arrays.toString(arr));
System.out.println();
}
System.out.println("冒泡排序：" + Arrays.toString(arr));
}
}
|
5. 冒泡排序的时间复杂度
冒泡排序的时间复杂度为O(n^2)，其中n为数组的长度。这是因为在最坏的情况下，需要进行n轮遍历，每轮遍历的比较次数为n-1。
6. 总结
冒泡排序虽然简单，但在大规模数据集上性能较差，不适合处理大量数据。然而，它的思想易于理解，是初学者学习排序算法的良好起点。在实际应用中，更高效的排序算法如快速排序、归并排序通常被优先选择。
