当前位置：Java冒泡排序及其性能优化
2018/11/12 15:25 分类： 技术交流 浏览：29
冒泡排序是各种语言中的经典排序案例。
冒泡排序核心思想：每一轮比较都能得到剩余元素中的最大值。
冒泡排序核心操纵:相邻元素两两比较，如果前面元素的值大于后面元素的值则交换两个元素。
1.常见版本：代码清单1：
import java.util.Arrays;
/**
* 实现冒泡排序
* @author lv
*
*/
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {1,200,19,55,10,22,3,7};
//API实现
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
//冒泡实现
for(int i =0;i<arr.length-1;i++){
for(int j = 0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
int temp = arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
}
2.外层循环优化版：
问题：
有的冒泡经过第一轮的交换已经是有序的了，如：2 1 3 4。数据越多的时候越慢，非常不适合大数据的排序解决办法
如果用一个flag来判断一下，当前数组是否已经有序，如果有序就退出循环，这样可以明显的提高冒泡排序的性能。
代码清单2：
package bubbleSort;
import java.util.Arrays;
import org.junit.Test;
/**
* 冒泡排序的性能分析和算法优化（外层循环优化）
* @author lv
*
*/
public class BubbeSort02 {
@Test
public void test1(){
boolean flag = true;
int[] arr = {2,1,3,4,5};
for (int i = 0; i < arr.length-1; i++) {
for (int j = 0; j < arr.length-1-i; j++) {
if(arr[j]>arr[j+1]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
flag=false;
}
}
if(!flag){
//没有发生交换则退出循环；
break;
}
}
System.out.println(Arrays.toString(arr));
}
}
3.内层循环优化代码清单3：
/**
* 冒泡排序的性能分析和算法优化（内层循环优化）
*/
@Test
public void test2(){
int[] arr = {22,1,10,5};
//标记最后一次交换的位置
for (int i = 0; i < arr.length-1; i++) {
int flag = 0;
int temp;
for (int j = 0; j < arr.length-i-1; j++) {
if(arr[j]>arr[j+1]){
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
//当位置发生改变，flag的值就发生变化
flag=1;
}
}
//判断标志位flag有没有发生变化，没有就直接结束内层循环
if(flag==0){
return;
}
}
System.out.println(Arrays.toString(arr));
}
}
赞 0
