冒泡排序

1 基本原理

我的理解是冒泡排序如同水中的气泡上浮一样，每次最大的元素浮到数组的最末端，每次排定一个元素。更加详细的请移步冒泡排序

2 基本步骤

1.比较相邻的元素，从第一对到最后一对，将较大的元素交换到一对的后面的元素。比如6 5，那么就交换为 5 6
2.完成上一步后，数组末尾的元素是最大的元素，此元素已经排定的
3.重复第一步，把最后一个元素忽略掉
4.如果没有了交换或者所有元素都已排定则说明排序完成

3 具体实现

public static void BubbleSort(int[] arr){
        int hi = arr.length - 1;
        for (int i = 0; i <= hi; i++) {
            for (int j = 0; j < hi-i; j++) {
                if(!SortUtil.less(arr,j,j+1)){
                    SortUtil.swap(arr,j,j+1);
                }
            }
         }
}

改进一
考虑到如果没有了交换 则说明所有元素位置已经是正确的，则可以直接退出循环，这种方式适合基本有序的数组

public static void BubbleSort(int[] arr){
        int hi = arr.length - 1;
        for (int i = 0; i <= hi; i++) {
            boolean changed = false;
            for (int j = 0; j < hi-i; j++) {
                if(!SortUtil.less(arr,j,j+1)){
                    SortUtil.swap(arr,j,j+1);
                    changed = true;
                }
            }
            if(changed == false){
                break;
            }
        }
    }

4 算法分析

使用了双层循环，复杂度为o(n^2)，是稳定的排序，因为相同大小的元素没有必要交换