冒泡排序

冒泡排序

• O(n^2)的排序算法
• 每次比较相邻两个元素

public class BubbleSort(){
    
    private BubbleSort(){}

    public static <E extends Comparable<E>> void sort(E[] data){
        for(int i=0;i<data.length-1;i++){
            for(int j=0;j<data.length-i-1;j++){
                if(data[j].compareTo(data[j+1])>0){
                    swap(data,j,j+1);
                }
            }
        }
    }
}

• 优化1-提前结束排序

public static <E extends Comparable<E>> void sort2(E[] data){
    for(int i=0;i<data.length-1;i++){
        boolean swapped=false;
        for(int j=0;j<data.length-i-1;j++){
            if(data[j].compareTo(data[j+1])>0){
                swap(data,j,j+1);
                swapped=true;
            }
        }
        if(!swapped){
            break;
        }
    }
}

• 优化2-记录交换位置

public static <E extends Comparable<E>> void sort3(E[] data){
    for(int i=0;i<data.length-1;){
        int index = 0;
        for(int j=0;j<data.length-i-1;j++){
            if(data[j].compareTo(data[j+1])>0){
                swap(data,j,j+1);
                index = j+1;
            }
        }
        i = data.length-index;
    }
}