冒泡排序

介绍

  1. 开始交换的区间是0~N-1,即数组整体:
    6 3 5 7 0 4 1 2—>第一个数和第二个数比较,哪个大哪个就放在后面,第二个数和第三个数比较,哪个大哪个放在后面,这样一次冒泡以后,最大的数就排在了数组的最后面。
  2. 再对0~N-2的区间进行同样的操作:
    3 5 6 0 4 1 2 7—>
  3. 依次进行,直到区间只有一个元素的时候,整个数组就变得有序了。

指标

时间复杂度 O(n²)
空间复杂度O(1)

代码

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
public class BubbleSort {
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
//每次都是0,1换;然后1,2换;然后2,3……类推。最大的数换到最后面----
for (int e = arr.length - 1; e > 0; e--) {
//终点前移--------------------
for (int i = 0; i < e; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
}
}
}
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
private static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = new int[] {3,5,4,2,6,7,1,9,8};
bubbleSort(arr);
printArray(arr);
}
}

输出

image

> >