冒泡排序是最基础的排序算法。
冒泡排序的英文是bubble sort,它是一种基础的交换排序。
冒泡排序这种排序算法的每一个元素都可以像小气泡一样,根据自身大小,一点一点地向着数组的一侧移动。
按照冒泡排序的思想,我们要把相邻的元素两两比较,当一个元素大于右侧相邻元素时,交换它们的位 置;当一个元素小于或等于右侧相邻元素时,位置不变。
经过第一轮后: 元素9作为数列中最大的元素,就像是汽水里的小气泡一样,“漂”到了最右侧。
每一轮结束都会有一个元素被移到最右侧。
1、冒泡算法
public static void main(String[] args) {
int[] array = {1,6,2,5,3,0,3,5,4};
array = bubbleSortBySortedExchanged(array);
for(int i =0 ; i < array.length; i++){
System.out.println(array[i]);
}
}
public static int[] bubbleSort(int[] array){
//有array.length-1个数字需要交换
for(int i = 0; i < array.length - 1; i++){
//每个数字比较的次数是array.length-1-i
for(int j = 0; j < array.length - 1 - i; j++){
//如果当前值大于后一个值,则将更大的值移到后一位
if(array[j] > array[j+1]){
swap(array[j],array[j+1]);
}
}
}
return array;
}
//互相交换值
public static void swap(int a,int b){
int temp = a;
a = b;
b = temp;
}
2、冒泡算法优化
(1)外层优化
第6轮已经可以结束了,也就是如果不需要交换了,则说明已经排好序了
思路:在外层循环处,设置标志isSort,默认为排好,如果不交换则跳出本次循环
(2)内部优化
已经被移到右侧的元素不用再参与比较了
思路:设置lastExchangeIndex标志单轮比较中最后一次比较的数值下标,下一轮比较就以lastExchangeIndex结束。
private static int[] bubbleSortBySortedExchanged(int[] array){
if(array == null || array.length < 2){
return array;
}
//单轮比较中最后一次交换的数值下标
int lastExchangeIndex = 0;
int sortBorder = array.length - 1;
//不交换则表示已排好
boolean isSorted = true;
for(int i = 0 ;i < array.length - 1; i++){
for(int j = 0; j < sortBorder ; j++){
if(array[j] > array[j+1]){
isSorted = false;
int temp = array[j+1];
array[j+1] = array[j];
array[j] = temp;
lastExchangeIndex = j;
}
}
sortBorder = lastExchangeIndex;
if(isSorted){
break;
}
}
return array;
}
时间复杂度:O( n的2次方 )
空间复杂度:O(1),也就是原地排序
稳定性:相等元素之间原有的先后顺序不变,也就是稳定排序