黑马程序员技术交流社区
标题:
冒泡排序和选择排序
[打印本页]
作者:
随性
时间:
2019-9-23 16:50
标题:
冒泡排序和选择排序
1、冒泡排序：
冒泡排序这种方法的基本思想是，将待排序（未排序序列）的记录看作是竖着排列的“气泡”，键值较小（数值较大）的记录比较轻，从而要往上浮。在冒泡排序算法中要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的记录的顺序是否正确。如果发现两个相邻记录的顺序不对，即“轻”（数值较大）的记录在下面，就变换它们的位置。显然，处理一遍之后，“最轻”的记录就浮到了最高位置，处理 i 遍之后，“次轻”的记录就浮到了次高位置。在作第 i 遍处理时，由于最高位置上的记录已是“最轻”记录，所以不必检查。一般地，第 i 遍处理时，不必检查第 i 高位置以上的记录。
简单来说，冒泡排序就是内循环中相邻两个数进行比较，若第 j 位比第 j+1 位的数大则交换两个数的位置。
动画演示如图：
实现代码：
/**
* 冒泡排序
*/
public class Sort3 {
public static void main(String[] args) {
//定义数组
int a[] = {5, 3, 6, 2, 4, 1, 9, 8, 0, 7};
int n;
// 将外循环的长度定义为数组的长度-1，最后两位只比较一次就可以
for(int i = 0; i < a.length - 1; i ++) {
//将内循环的长度定义为数组的长度-1-i，已排好序的序列不用再循环
for (int j = 0; j < a.length - 1 - i; j ++) {
//比较相邻两个数的值，若第j位>第j+1位，则两个数交换
if (a[j] > a[j+1]) {
n = a[j];
a[j] = a[j + 1];
a[j + 1] = n;
}
}
//每外循环完成一次，就打印一次结果
for (int m = 0; m < a.length; m ++) {
System.out.print(a[m] + " ");
}
System.out.println();
}
}
}
运行结果：
3 5 2 4 1 6 8 0 7 9
3 2 4 1 5 6 0 7 8 9
2 3 1 4 5 0 6 7 8 9
2 1 3 4 0 5 6 7 8 9
1 2 3 0 4 5 6 7 8 9
1 2 0 3 4 5 6 7 8 9
1 0 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
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
2、选择排序：
从待排序的元素中选出最小(大)的元素放在起始位置,然后再从剩余的元素中选出最小(大)的元素放在已排好的部分之后,直到只剩最后一个待排序的元素为止。
简单来说，选择排序就是用外循环的 i 值（基准值）与内循环的 j 值（需要进行比较的值）逐一比较，并将最小（大）的数放在前面。
动画演示如图：
实现代码：
/**
* 选择排序有小到大进行排序
*/
public class Sort2 {
public static void main(String[] args) {
//定义数组
int a[] = {5, 3, 6, 2, 4, 1, 9, 8, 0, 7};
int n;
// 将外循环的长度定义为数组的长度-1，最后两位只比较一次就可以
for (int i = 0; i < a.length - 1; i ++) {
//将内循环的长度定义为数组的长度，j = i + 1表示已排好序的序列不用再循环
for (int j = i + 1; j < a.length; j ++) {
//将外循环的数第 i 位与内循环的数 j 逐一比较，若第 i 位>第 j 位，则两个数进行交换
if (a[i] > a[j]){
n = a[i];
a[i] = a[j];
a[j] = n;
}
}
//每外循环完成一次，就打印一次结果
for (int j = 0; j < a.length; j ++) {
System.out.print(a[j] + " ");
}
System.out.println();
}
}
}
运行结果：
0 5 6 3 4 2 9 8 1 7
0 1 6 5 4 3 9 8 2 7
0 1 2 6 5 4 9 8 3 7
0 1 2 3 6 5 9 8 4 7
0 1 2 3 4 6 9 8 5 7
0 1 2 3 4 5 9 8 6 7
0 1 2 3 4 5 6 9 8 7
0 1 2 3 4 5 6 7 9 8
0 1 2 3 4 5 6 7 8 9
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
3、选择排序与冒泡排序总结：
（1）、冒泡排序就是内循环中相邻两个数进行比较，若第 j 位比第 j+1 位的数大则交换两个数的位置。
（2）、选择排序就是用外循环的 i 值（基准值）与内循环的 j 值（需要进行比较的值）逐一比较，并将最小（大）的数放在前面。
（3）、通过上述代码进行对比会发现选择排序和冒泡排序有许多相似的地方，说明这两个排序有相通的地方，两者不是一点都不相通的。
（4）、从运行结果看，外循环每循环完一次后的排序结果来说，冒泡排序是呈右直角三角形的，选择排序是呈左直角三角形的，不过选择排序结果也可以呈右直角三角形，冒泡排序结果也可以呈左直角三角形。
以选择排序为例：
/**
* 先将选择排序由大到小排序
* 再将排序好的选择排序倒序输出
*/
public class Sort2 {
public static void main(String[] args) {
int a[] = {5, 3, 6, 2, 4, 1, 9, 8, 0, 7};
int n;
for (int i = 0; i < a.length - 1; i ++) {
for (int j = i + 1; j < a.length; j ++) {
//将选择排序由大到小排序
if (a[i] < a[j]){
n = a[i];
a[i] = a[j];
a[j] = n;
}
}
//每外循环完成一次，就倒序打印数组一次结果
for (int j = a.length-1; j >= 0; j --) {
System.out.print(a[j] + " ");
}
System.out.println();
}
}
}
运行结果：
7 0 8 6 1 4 2 5 3 9
7 0 6 5 1 4 2 3 8 9
6 0 5 4 1 3 2 7 8 9
5 0 4 3 1 2 6 7 8 9
4 0 3 2 1 5 6 7 8 9
3 0 2 1 4 5 6 7 8 9
2 0 1 3 4 5 6 7 8 9
1 0 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2