算法思想:
核心:
拿着左边的数字和右边的数字比对,当左边 > 右边的时候,交换位置。
算法步骤:
比较相邻的元素。如果第一个比第二个大,就交换他们两个。
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
针对所有的元素重复以上的步骤,除了最后一个。
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
代码
for(int i = arr.length - 1; i > 0; i--){
for(int j = 0; j < i; j++){
if(arr[j] > arr[j + 1]){
// 交换位置。
// arr[j] 和 arr[j+1] 交换
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
比较次数:(n(n + 1)) / 2
过程
参与比较的数据:9 8 10 7 6 0 11
第1次循环:
8 9 10 7 6 0 11 (第1次比较:交换)
8 9 10 7 6 0 11 (第2次比较:不交换)
8 9 7 10 6 0 11 (第3次比较:交换)
8 9 7 6 10 0 11 (第4次比较:交换)
8 9 7 6 0 10 11 (第5次比较:交换)
8 9 7 6 0 10 11 (第6次比较:不交换)
最终冒出的最大数据在右边:11
参与比较的数据:8 9 7 6 0 10
第2次循环:
8 9 7 6 0 10(第1次比较:不交换)
8 7 9 6 0 10(第2次比较:交换)
8 7 6 9 0 10(第3次比较:交换)
8 7 6 0 9 10(第4次比较:交换)
8 7 6 0 9 10(第5次比较:不交换)
参与比较的数据:8 7 6 0 9
第3次循环:
7 8 6 0 9(第1次比较:交换)
7 6 8 0 9(第2次比较:交换)
7 6 0 8 9(第3次比较:交换)
7 6 0 8 9(第4次比较:不交换)
参与比较的数据:7 6 0 8
第4次循环:
6 7 0 8(第1次比较:交换)
6 0 7 8(第2次比较:交换)
6 0 7 8(第3次比较:不交换)
参与比较的数据:6 0 7
第5次循环:
0 6 7(第1次比较:交换)
0 6 7(第2次比较:不交换)
参与比较的数据:0 6
第6次循环:
0 6 (第1次比较:不交换)
循环次数:n - 1
冒泡排序还有一种优化算法,就是立一个 flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。
代码
for(int i = arr.length - 1; i > 0; i--){
int flag = 0;//将flag初始置为0
for(int j = 0; j < i; j++){
if(arr[j] > arr[j + 1]){
// 交换位置。
// arr[j] 和 arr[j+1] 交换
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = 1;//发生交换将flag置为1
}
}
if(flag == 0) break;//flag为0表示本轮没有元素发生交换,证明已经排好序了,直接跳出循环
}