冒泡排序是一种 交互排序
交换排序:两两比较待排序的关键字,并交互不满足次序要求的那对数,直到整个表满足次序要求为止
直接上例子:
例如:{2,3,5,1,4}
第一趟:两两比较,找到第一小数值为1,排到第一位
第二趟:两两比较,找到第二小数值为2,由于2,3已经是存在的顺序
第三趟:两两比较,找到第四小数值为4,排到第4位
至此结束
思路: 假设对一个大小为n的数组进行从小到大的排序
(1) 每趟排序过程中需要通过两两比较找到第i个小的元素
所以我们,需要一个外部循环,从数组的首端(下标为 0) 开始
一直到倒数第二个元素(即下标为N-2),剩下的为最大元素
(2)假设是第i趟排序，可知，前i-1个元素已经有序，现在要找第i个元素，
只需从数组末端开始，扫描到第i个元素，将它们两两比较即可。
所以，需要一个内部循环，从数组末端开始，下标（N-1），扫描到（下标i+1）
核心 代码如下：
int[] source ={8,7,9,5,6,3,2,1,4,5};
sort(source);
public static void sort(int[] source){
int temp =0;
//要遍历的次数
for(int i=0;i<source.length-1;i++){
// 两两比较
for(int j= source.length-1;j>i;j--){
if(source[j-1]>source[j]){
temp =source[j-1];
source[j-1] = source[j];
source[j] =temp;
}
}
System.out.format("第 %d 趟 \t", i);
printlnAll(source);
}
}
private static void printlnAll(int[] source) {
for(int value : source ){
System.out.print(value +" ");
}
System.out.println();
}
}
效果如下：
第 0 趟 1 8 7 9 5 6 3 2 4 5
第 1 趟 1 2 8 7 9 5 6 3 4 5
第 2 趟 1 2 3 8 7 9 5 6 4 5
第 3 趟 1 2 3 4 8 7 9 5 6 5
第 4 趟 1 2 3 4 5 8 7 9 5 6
第 5 趟 1 2 3 4 5 5 8 7 9 6
第 6 趟 1 2 3 4 5 5 6 8 7 9
第 7 趟 1 2 3 4 5 5 6 7 8 9
第 8 趟 1 2 3 4 5 5 6 7 8 9
算法分析
冒泡排序算法的性能
image.png
时间复杂度
若排序都是正序，一趟就可以完成排序，比较次数
C和记录移动次数M均达到最小值：Cmin = N-1,Mmin = 0 ，所以，冒泡排序最好时间复杂度为O（N）
若排序正好是反序，需要进行N-1趟排序，每趟排序进行N-i次关键字的比较，且每次都需要移动三次来达到交互记录位置，利用临时变量，此时的移动次数到达最大值
Cmax=N（N-1）/2 =O（N2）
Mmax=3N(N-1)/2 = O(N2)
冒泡排序的最坏时间复杂度O（N2）
因此，冒泡排序的平均时间复杂度O（N2）
总结，数据越接近正序，冒泡排序性能越好
算法的稳定性
冒泡排序就是把小的元素往前或者大的后调，比较是两个元素之前的，交换也是发生在这两个元素之间。
所以相同元素的前后顺序并没有发生改变，所以相对来说冒泡排序比较稳定
优化
对冒泡排序常见的改进方法是加入标志性变量exchange，用于标志某一趟排序过程中是否有数据交换。
如果进行某一趟排序时并没有进行数据交换，则说明所有数据已经有序，可立即结束排序，避免不必要的比较过程。
public static void sort2(int[] source) {
int temp = 0;
boolean exchang = false;// 交换标志
// 要遍历的次数
for (int i = 0; i < source.length - 1; i++) {
// 两两比较
for (int j = source.length - 1; j > i; j--) {
if (source[j - 1] > source[j]) {
temp = source[j - 1];
source[j - 1] = source[j];
source[j] = temp;
exchang = true;
}
}
// 如果标志为false，说明本轮遍历没有交换，已经是有序数列，可以结束排序
if (!exchang) {
break;
}
System.out.format("优化后 第 %d 趟 \t", i);
printlnAll(source);
}
}
private static void printlnAll(int[] source) {
for (int value : source) {
System.out.print(value + " ");
}
System.out.println();
}
网友评论