【面试：基础篇02：冒泡排序】
介绍
冒泡排序顾名思义是一种排序算法 与相邻元素比较 然后交换 因为没一趟的最大/最小值 最终会排序到当前趟的最后位置 所以形象的称为冒泡排序，是排序算法中比较基础的一种，这就意味着我们必须掌握。
案例推理
对本数列 {5,2,7,4,1,3,8,9} 进行冒泡排序 顺序从小到大
第一趟
2 5 4 1 3 7 8 9，比较了7次，确定了9是当前趟最后位
第二趟
2 4 1 3 5 7 8 9，比较了6次，确定了8是当前趟最后位
第三趟
2 1 3 4 5 7 8 9，比较了5次，确定了7是当前趟最后位
第四趟
1 2 3 4 5 7 8 9，比较了4次，确定了5是当前趟最后位
第五趟
1 2 3 4 5 7 8 9，比较了3次，确定了4是当前趟最后位
第六趟
1 2 3 4 5 7 8 9，比较了2次，确定了3是当前趟最后位
第七趟
1 2 3 4 5 7 8 9，比较了1次，确定了2是当前趟最后位
完成排序
这个案例告诉了我们什么
第一：我们发现了 8个元素 需要7趟排序。
第二：我们发现了 每趟排序只需要比较当前趟没有确定的元素 确定的元素无需比较，即每趟只需比较 ==元素个数-当前趟数== 例如第三趟我们只需要比较 8-3次 因为前两趟已经确定两个值 我们只需要在剩下六个中比较五次 就可以确定第三趟的极值。
第三：我们发现了第四趟就已经排序完成了，但仍然又比较了三趟，这是我们的优化点之一，优化趟数。
第四：我们发现了每趟的次数也可以优化，例如第二趟我们比较了六次，但其实在第一趟比较时就已经确定了7 8 9三个最大值，所以我们其实只用比较剩下5个元素，也就是只需要比较四次，因为我们每趟的次数也减少，所以我们最终的趟数也会随之减少。
算法1 无优化
代码
public static void main(String[] args) {
int[] a = {5,2,7,4,1,3,8,9};
int len = a.length;
for(int i=0;i<len-1;i++){
int cnt=0;
System.out.println("第"+(i+1)+"趟");
for (int j=0;j<len-i-1;j++){
if(a[j]>a[j+1]){
int t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
cnt++;
}
for (int k=0;k<len;k++)
System.out.printf("%d ",a[k]);
System.out.printf("比较次数:%d\n",cnt);
}
}结果
第1趟
2 5 4 1 3 7 8 9 比较次数:7
第2趟
2 4 1 3 5 7 8 9 比较次数:6
第3趟
2 1 3 4 5 7 8 9 比较次数:5
第4趟
1 2 3 4 5 7 8 9 比较次数:4
第5趟
1 2 3 4 5 7 8 9 比较次数:3
第6趟
1 2 3 4 5 7 8 9 比较次数:2
第7趟
1 2 3 4 5 7 8 9 比较次数:1可以看出无优化版本和我们的推理一模一样
算法2 优化趟数
优化思路
观察上述例子 我们可以看出主要问题在于当完全排序后 趟数并没有随之停止而是继续比较了三趟，针对这个问题我们有了这个思路：不难想到 在完全排序后 每趟中 必不可能出现交换的情况 因为以及有序了 相邻元素 都不满足交换情况 所以我们只有判断如果 一次交换都没有 则可以证明 完全排序了
代码
public static void main(String[] args) {
int[] a = {5,2,7,4,1,3,8,9};
int len = a.length;
for(int i=0;i<len-1;i++){
int cnt=0;
boolean flag=false;// 判断是否有交换
System.out.println("第"+(i+1)+"趟");
for (int j=0;j<len-i-1;j++){
if(a[j]>a[j+1]){
int t = a[j];
a[j] = a[j+1];
a[j+1] = t;
flag=true;
}
cnt++;
}
for (int k=0;k<len;k++)
System.out.printf("%d ",a[k]);
System.out.printf("比较次数:%d\n",cnt);
if (!flag)
break;
}
} 结果
第1趟
2 5 4 1 3 7 8 9 比较次数:7
第2趟
2 4 1 3 5 7 8 9 比较次数:6
第3趟
2 1 3 4 5 7 8 9 比较次数:5
第4趟
1 2 3 4 5 7 8 9 比较次数:4
第5趟
1 2 3 4 5 7 8 9 比较次数:3
可以看出趟数减少了两次，但最后不是在第四趟停止的原因是 第四趟进行了交换 真正不交换是在第五次。
算法3 优化趟数与次数
优化思路
这个问题的优化点在：例如 第一趟时 8 9 最开始就是最大的两个值 所以我们进行比较时最后的结果是7 8 9 第二趟我们再次比较 会把 7 8 再比较一次 但我们已经确定了 7 8 9就是最大的值了，所以我们的优化思路是 我们记录一下最后一一次交换的索引，比如 在第一趟排序时 最后交换的是7 3 也就是数组下标4 数组下标4后的元素都是排序好的 所以我们第二趟排序 只用比较到 数组下标4这个位置 也就是只需要比较4次 直接少了两次，如果最后的交换下标是0 说明我们排序完成。因为我们的每趟需要比较的次数比先前少 导致我们的趟数也会随着减少，因为原来每一趟比较次数只是减少1次，而现在我们每趟减少的都>=1次所以趟数随之减少。
再理解：最后一次排序一定是当前趟数的最大值 且 之前趟数一定都已经排好了 所以我们才能 下一次才可以只需要比较到最后一次排序的那个位置
代码
int[] a = {5,2,7,4,1,3,8,9};
int len = a.length;
int n=len-1;
int i=0;
while (true) {
System.out.println("第"+(++i)+"趟");
int pos=0;//临时记录最后交换的位置下标
int cnt=0;
for(int j=0;j<n;j++){
if(a[j]>a[j+1]){
int t = a[j];
a[j] = a[j+1];
a[j+1] = t;
pos=j;
}
cnt++;
}
n=pos;//真正记录最后位置的下标
for (int k=0;k<len;k++)
System.out.printf("%d ",a[k]);
System.out.printf("比较次数:%d\n",cnt);
if (n==0)
break;
}结果
第1趟
2 5 4 1 3 7 8 9 比较次数:7
第2趟
2 4 1 3 5 7 8 9 比较次数:4
第3趟
2 1 3 4 5 7 8 9 比较次数:3
第4趟
1 2 3 4 5 7 8 9 比较次数:2
可以看出我们的比较次数与排序趟数都减少很多
