冒泡排序

什么是冒泡排序？

冒泡排序的英文Bubble Sort，是一种最基础的交换排序。

相信大家都见过气泡从水里冒起来的过程，小气泡一点一点向上浮动，随着浮动气泡也越来越大。冒泡排序之所以叫冒泡排序，正式因为这种排序方式的每一个元素就像气泡一样，一点一点向数组的一侧移动。
冒泡排序的思想，我们要把相邻的元素两两比较，根据大小来交换元素的位置，每次只能得出一个位置，因此排序需要n-1趟

public class 冒泡 {

public static void bubbleSort(int[] arr) {
    if(arr == null || arr.length<2) {
        return;
    }
    for(int end=arr.length-1;end>0;end--) {
        for(int i = 0;i < end; i++) {
            if(arr[i]>arr[i+1]) {
                swap(arr,i,i+1);
            }
        }
    }
}

public static void swap(int[] arr,int i,int j) {
    int tmp = arr[i];
    arr[i]=arr[j];
    arr[j]=tmp;
}
    
public static void main(String[] args) {
    int[] arr = {23,32,6,5,9,556,4,8,59,7,8,9};
    bubbleSort(arr);
    System.out.println(Arrays.toString(arr));

}

}

代比较简单，使用双循环来进行排序。外部循环控制所有的回合，内部循环代表每一轮的冒泡处理，先进行元素比较，再进行元素交换。

由于有的数组在经过几轮的排序后其中一部分就变为有序的了，但这时代码并不能识别，那么我们就可以进行优化，让他能够进行识别,剩下的几轮排序就可以不必执行这样就能提早结束工作！代码如下：

public class 冒泡 {

public static void bubbleSort(int[] arr) {
    if(arr == null || arr.length<2) {
        return;
    }
    boolean isSort= true; 
    for(int end=arr.length-1;end>0;end--) {
        for(int i = 0;i < end; i++) {
            if(arr[i]>arr[i+1]) {
                swap(arr,i,i+1);
                isSort = false;
            }
        }
        //判断是否每一轮都为无序
        if(isSort)
            break;
    }
}

public static void swap(int[] arr,int i,int j) {
    int tmp = arr[i];
    arr[i]=arr[j];
    arr[j]=tmp;
}
    
public static void main(String[] args) {
    int[] arr = {23,32,6,5,9,556,4,8,59,7,8,9};
    bubbleSort(arr);
    System.out.println(Arrays.toString(arr));

}

}

在排序中，元素有交换，则说明数列无序；如果没有元素交换，说明数列已然有序，直接跳出大循环。