Java之基本排序算法
sunshj Lv4

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++) {
// 设定一个标记,若为true,则表示此次循环没有进行交换,也就是待排序列已经有序,排序已经完成。
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();
}
}
}
 评论