一、排序思想
冒泡排序是一种典型的交换排序,类似于水中冒泡,较大的数沉下去,较小的数慢慢冒起来,假设从小到大,即为较大的数慢慢往后排,较小的数慢慢往前排。
冒泡排序的思想就是利用的比较交换,利用循环将第 i 小或者大的元素归位,归位操作利用的是对 n 个元素中相邻的两个进行比较,如果顺序正确就不交换,如果顺序错误就进行位置的交换。通过重复的循环访问数组,直到没有可以交换的元素,那么整个排序就已经完成了。
二、算法分析与图解
依次比较相邻的两个数,将比较小的数放在前面,比较大的数放在后面。
(1) 第一次比较:首先比较第一和第二个数,将小数放在前面,将大数放在后面。
(2) 比较第2个数和第3个数,将小数放在前面,大数放在后面。
.....
(3) 如此继续,直到比较到最后的两个数,将小数放在前面,大数放在后面,第一次比较完成。
(4) 第一次比较完成后,开始第二次比较,重复上述步骤,直至数组全部排序完成。
(5) 在上面一趟比较完成后,最后一个数一定是数组中最大的一个数,所以在比较第二趟的时候,最后一个数是不参加比较的。
(6) 在第二趟比较完成后,倒数第二个数也一定是数组中倒数第二大数,所以在第三趟的比较中,最后两个数是不参与比较的。
(7) 依次类推,每一趟比较次数减少一次
演示动图
(图源网络,侵权请联系删除)
三、举例说明
举例,原始数组为 [60, 55, 41, 13, 25, 37, 23]
3.1 第一趟排序
比较次数 |
判定 |
结果 |
第1次比较 |
60和55比较,60大于55,所以交换位置 |
[55,60,41,13,25,37,23 ] |
第2次比较 |
60和41比较,60大于41,所以交换位置 |
[55,41,60,13,25,37,23 ] |
第3次比较 |
60和13比较,60大于12,所以交换位置 |
[55,41,13,60,25,37,23 ] |
第4次比较 |
60和25比较,60大于25,所以交换位置 |
[55,41,13,25,60,37,23 ] |
第5次比较 |
60和37比较,60大于37,所以交换位置 |
[55,41,13,25,37,60,23 ] |
第6次比较 |
60和23比较,60大于23,所以交换位置 |
[55,41,13,25,37,23,60 ] |
3.2 第二趟排序
比较次数 |
判定 |
结果 |
第1次比较 |
41和55比较,55大于41,交换位置 |
[41,55,13,25,37,23,60 ] |
第2次比较 |
55和13比较,55大于13,交换位置 |
[41,13,55,25,37,23,60 ] |
第3次比较 |
55和25比较,55大于25,交换位置 |
[41,13,25,55,37,23,60 ] |
第4次比较 |
55和37比较,55大于37,交换位置 |
[41,13,25,37,55,23,60 ] |
第5次比较 |
55和23比较,55大于23,交换位置 |
[41,13,25,37,23,55,60 ] |
3.3 第三趟排序
比较次数 |
判定 |
结果 |
第1次比较 |
41和13比较,41大于41,交换位置 |
[13,41,25,37,23,55,60 ] |
第2次比较 |
41和25比较,41大于25,交换位置 |
[13,25,41,37,23,55,60 ] |
第3次比较 |
41和37比较,41大于37,交换位置 |
[13,25,37,41,23,55,60 ] |
第4次比较 |
41和23比较,41大于23,交换位置 |
[13,25,37,23,41,55,60 ] |
3.4 第四趟比较
比较次数 |
判定 |
结果 |
第1次比较 |
13和25比较,13小于25,位置不变 |
[13,25,37,23,41,55,60 ] |
第2次比较 |
25和37比较,25小于37,位置不变 |
[13,25,37,23,41,55,60 ] |
第3次比较 |
37和23比较,37大于23,交换位置 |
[13,25,23,37,41,55,60 ] |
3.5 第五趟排序
比较次数 |
判定 |
结果 |
第1次比较 |
13和25比较,13小于25,位置不变 |
[13,25,23,37,41,55,60 ] |
第2次比较 |
25和23比较,25大于23,交换位置 |
[13,23,25,37,41,55,60 ] |
3.6 第六趟排序
比较次数 |
判定 |
结果 |
第1次比较 |
13和25比较,13小于25,位置不变 |
[13,23,25,37,41,55,60 ] |
最终结果
排序完成后,数组排列如图所示:
三、代码实现
/**
* 冒泡排序
* @param arr
*/
private static void bubbleSort(int[] arr) {
if(arr==null || arr.length < 2 )
return;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i -1; j++) {
if (arr[j] > arr[j + 1]) {
flag = true;
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
四、优化
冒泡排序的思想就是大的往上挪动,可是如果已经是一个排好序的数组,还需要继续冒泡吗?
答案肯定是不需要的,所以我们需要对其进行优化。
如果判定已经是一个有序数组,直接终止排序即可。
/**
* 冒泡排序
* @param arr
*/
private static void bubbleSort(int[] arr) {
boolean flag = false;
if(arr==null || arr.length < 2 )
return;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i -1; j++) {
if (arr[j] > arr[j + 1]) {
flag = true;
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
if(!flag)
break;
flag = false;
}
}