数据结构与算法：冒泡排序

作者：日拱一卒程序猿 2023-03-02 08:15:13开发 前端 按照冒泡排序的数据算法思想，我们要把相邻的结构元素两两比较，当一个元素大于右侧相邻元素时，冒泡交换它们的排序位 置；当一个元素小于或等于右侧相邻元素时，位置不变。数据算法

一、结构定义

冒泡排序是冒泡最基础的排序算法。

冒泡排序的排序英文是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)，也就是原地排序

稳定性:相等元素之间原有的先后顺序不变，也就是稳定排序

责任编辑：武晓燕 来源： 今日头条 数据结构算法冒泡排序

(责任编辑：探索)