Java实现冒泡排序

冒泡排序(基础版本)

//冒泡（两轮循环，外层表示第几轮冒泡，内层表示两两比较）
    public static void bubble(int[] a){
        //冒泡轮次
        for (int j = 0; j < a.length - 1; j++){
            //两两比较
            for (int i = 0; i < a.length -j -1; i++){
                if(a[i] > a[i + 1]){
                    swap(a, i, i+1);
                }
            }
        }
    }  

冒泡排序（优化版）

/*优化版本
（判断本轮冒泡是否发生了交换，
    如果没有发生交换则说明集合已经有序，不再需要后面的冒泡）*/
    public static void bubble_v2(int[] a){
        for (int j = 0; j < a.length - 1; j++){
            boolean swapped = false;//是否发生了交换
            for (int i = 0; i < a.length -j -1; i++){
                if(a[i] > a[i + 1]){
                    swap(a, i, i+1);
                    swapped = true;
                }
            }
            if(!swapped){
                break;
            }
        }
    } 

冒泡排序（最终版本）

/*最终优化本
    （记录最后一次交换索引last的位置，
    last之后的索引都是有序的不再需要两两判断，
    当last==0时说明集合已经有序）*/
    public static void bubble_v3(int[] a){
        int n = a.length - 1;
        while (true){
            int last = 0;//表示最后一次交换索引的位置
            //只比较最后一次交换索引之前的元素
            for(int i = 0; i < n; i++){
                if(a[i] > a[i + 1]){
                    swap(a, i, i+1);
                    last = i;
                }
            }
            n = last;
            if(n == 0){
                break;
            }
        }
    }

实现思路

以升序为例

• 1，依次比较数组中相邻两个元素大小，若a[j] > a[j+1],则交换两个元素，两两都比较一遍称为一轮冒泡，结果是让最大的元素排至最后。
• 2，优化方向：可每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，如果这个值为零，表示整个数组有序则直接退出外层循环。

附上swap（）交换方法

/**
     * 交换元素
     * @param a 数组
     * @param i 索引i
     * @param j 索引j
     */
    public static void swap(int[] a, int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }