基本思想
冒泡排序简单来说就是每一趟排序比较相邻两个元素值,大的交换到后面,那么一趟排序下来最大的元素被沉到最后。对剩下的元素重复以上操作,每一趟都将最大的元素沉到最后,直到所有元素有序。
代码实现
public void bubbleSort(int[] a){
int temp;
for(int i = 0; i < a.length - 1; i++){
for(int j = 0; j < a.length - 1 - i; j++){
if(a[j] > a[j + 1]){
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
时间复杂度
- 最好情况:O(n),若待排序序列全部有序,则只需进行一趟比较,若没有元素交换则结束排序。
- 平均情况:O(n*n)
算法改进
- 前面我们说到,冒泡排序在最好的情况下时间复杂度是O(n),但事实上前面贴的代码在元素全部有序的情况下时间复杂度依然是O(n*n),因为一趟排序下来我们并不知道这趟排序元素有没有交换。因此,我们需要添加一个标记位来标记一趟排序元素是否有交换。
public void bubbleSort(int[] a){
int temp;
boolean flag;
for(int i = 0; i < a.length - 1; i++){
flag = false;
for(int j = 0; j < a.length - 1 - i; j++){
if(a[j] > a[j + 1]){
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
flag = true;
}
}
if(flag == false){
break;
}
}
}
- 再做进一步的优化。如果有100个数的数组,仅前面10个无序,后面90个都已排好序且都大于前面10个数字,那么在第一趟遍历后,最后发生交换的位置必定小于10,且这个位置之后的数据必定已经有序了,记录下这位置,第二次只要从数组头部遍历到这个位置就可以了。
public void bubbleSort(int[] a){
int temp;
int lastSwapPos = a.length - 1;
int lastSwapPosTemp;
for(int i = 0; i < a.length - 1; i++){
lastSwapPosTemp = lastSwapPos;
for(int j = 0; j < lastSwapPosTemp; j++){
if(a[j] > a[j + 1]){
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
lastSwapPos = j;
}
}
if(lastSwapPosTemp == lastSwapPos){
break;
}
}
}