Java 数据结构与算法 - 基本排序：冒泡、插入、选择排序
在线排序算法可视化网站 - visualgo.net
问：现在给定一个数组，但是数组里面的数据是乱序排列的，如何使它变得有序？
1
| int[] arr = {5, 2, 7, 1, 3, 0, 8, 9, 4, 6};
|
一、冒泡排序
就是比较相邻的元素，如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，第一轮后最后的元素会是最大的数。重复进行以上步骤，但是已排序后的最大数、次大数等不应再继续进行比较，直到没有任何一对数字需要比较即可。
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
|
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {5, 2, 7, 1, 3, 0, 8, 9, 4, 6};
test(arr);
}
private static void test(int[] arr) {
for (int j = 0; j < arr.length - 1; j++) {
boolean flag = true;
for (int i = 0; i < arr.length - 1 - j; i++) {
if (arr[i] > arr[i + 1]) {
b = false;
int tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
}
}
if (flag) break;
for (int k : arr) {
System.out.print(k + " ");
}
System.out.println();
}
}
}
|
二、插入排序
插入排序其实就跟我们打牌是一样的，我们在摸牌的时候，牌堆是乱序的，但是我们一张一张摸到手中进行排序，使得它变成了有序的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public class InsertionSort {
public static void main(String[] args) {
int[] arr = {5, 2, 7, 1, 3, 0, 8, 9, 4, 6};
test(arr);
}
private static void test(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int tmp = arr[i];
int j = i - 1;
while (j >= 0 && tmp < arr[j]) {
arr[j + 1] = arr[j];
arr[j] = tmp;
j--;
}
for (int k : arr) {
System.out.print(k + " ");
}
System.out.println();
}
}
}
|
三、选择排序
选择排序其实就是每次都选择最小（或最大）的一个数，放在起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的数的后面。
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
|
public class SelectionSort {
public static void main(String[] args) {
int[] arr = {5, 2, 7, 1, 3, 0, 8, 9, 4, 6};
test(arr);
}
private static void test(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (min != i) {
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
for (int k : arr) {
System.out.print(k + " ");
}
System.out.println();
}
}
}
|
