冒泡排序的具体思想和算法实现以及改进

冒泡排序——稳定算法

从小到大排序：

0~length-1

对比a[0]和a[1]，如果前一个大于后一个，交换位置。

对比a[1]和a[2]，如果前一个大于后一个，交换位置。

对比a[2]和a[3]，如果前一个大于后一个，交换位置。

...

对比a[length-2]和a[length-1]，如果前一个大于后一个，交换位置。

第一轮结果下来就是把最大值放在了最后面。

0~length-2

对比a[0]和a[1]，如果前一个大于后一个，交换位置。

对比a[1]和a[2]，如果前一个大于后一个，交换位置。

对比a[2]和a[3]，如果前一个大于后一个，交换位置。

...

对比a[length-3]和a[length-2]，如果前一个大于后一个，交换位置。

第二轮结果下来就是把第二大值放在倒数第二个。

改进——记录最后一次交换的索引位置，作为下一次冒泡的比较次数 （该位置后的元素均已有序

Java代码如下： 

public class BubbleSort {

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 6, 2, 7, 1, 4};
        bubbleSort(arr);
    }
    private static void bubbleSort(int[] arr) {
        int n=arr.length-1;
        while(true){
//            最后一次交换索引的位置
            int last=0;
            for(int i=0;i<n;i++){
                if(arr[i+1]<arr[i]){
                    int temp=arr[i+1];
                    arr[i+1]=arr[i];
                    arr[i]=temp;
                    last=i;
                }
            }
            printArr(arr);
            n=last;
//            说明没交换过 即有序 不用再冒泡了
            if(n==0) break;
        }
    }
    private static void printArr(int[] arr){
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }
}