博客

算法-冒泡排序及Java代码实现

冒泡排序过程的文字描述

冒泡排序分析(升序)：
第一轮冒泡排序：
假设有n个元素。
1.指针指向第一个元素，第一个元素和第二个元素进行比较，若第一个元素比第二个元素大，
则互相交换数值（从而实现大的数值向后面移动）
2.指针指向第二个元素，第二个元素和第三个元素进行比较，若第二个元素比第三个元素大，
则互相交换数值
.....
3.指针指向第n-1个元素，第n-1个元素和第n个元素进行比较，若第n-1个元素比第n个元素大，
则互相交换数值，此时第一轮冒泡排序结束，最大的数也移动到了第n位

第二轮冒泡排序：
1.指针重新指向第一个元素，第一个元素和第二个元素进行比较，若第一个元素比第二个元素大，
则互相交换数值（从而实现大的数值向后面移动）
2.指针指向第二个元素，第二个元素和第三个元素进行比较，若第二个元素比第三个元素大，
则互相交换数值
.....
3.指针指向第n-2个元素，第n-2个元素和第n-1个元素进行比较，若第n-2个元素比第n-1个元素大，
则互相交换数值，此时第二轮冒泡排序结束，第二大的数也移动到了第n-1位（跟第一轮相比是不是
很熟悉的过程？并且有没有发现第二轮比较大小的次数比第一轮少一次）
.
.
.
一直重复进行下去，直到第二个元素也排序好了，第一个元素必然就是最小的数了，不需要再进行排序，
因此当元素为n个时，需要进行n-1轮冒泡排序的操作

初步代码实现

以需要六轮冒泡排序达到升序效果的实例为例：

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {11,43,22,54,37,82,7};
        System.out.println(Arrays.toString(arr));


//            要注意循环条件的设置，i是[0,length-1],但是判断条件里面有arr[i+1],
//            此时arr[i+1]的范围是[0,length]，但是arr[]的数据范围是[0,length-1]，
//            因此i应该：i < arr.length - 1，否则会发生数组越界：ArrayIndexOutOfBoundsException
        for (int i = 0; i < arr.length - 1; i++) {
            if(arr[i] > arr[i+1]){
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        }
        System.out.println("第一轮冒泡排序： " + Arrays.toString(arr));
        System.out.println("----------------------");

        for (int i = 0; i < arr.length - 1 - 1; i++) {
            if(arr[i] > arr[i+1]){
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        }
        System.out.println("第二轮冒泡排序： " + Arrays.toString(arr));
        System.out.println("----------------------");

        for (int i = 0; i < arr.length - 1 - 2; i++) {
            if(arr[i] > arr[i+1]){
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        }
        System.out.println("第三轮冒泡排序： " + Arrays.toString(arr));
        System.out.println("----------------------");

        for (int i = 0; i < arr.length - 1 - 3; i++) {
            if(arr[i] > arr[i+1]){
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        }
        System.out.println("第四轮冒泡排序： " + Arrays.toString(arr));
        System.out.println("----------------------");

        for (int i = 0; i < arr.length - 1 - 4; i++) {
            if(arr[i] > arr[i+1]){
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        }
        System.out.println("第五轮冒泡排序： " + Arrays.toString(arr));
        System.out.println("----------------------");

        for (int i = 0; i < arr.length - 1 - 5; i++) {
            if(arr[i] > arr[i+1]){
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        }
        System.out.println("第六轮冒泡排序： " + Arrays.toString(arr));
        System.out.println("----------------------");
    }

}

迭代优化

有没有发现一个问题，for循环部分高度重复，只有判断条件有细微变化，并且该变化呈现一定规律，因此我们可以进行优化，将这六个for循环继续用for循环装在一起，用for循环嵌套实现冒泡排序，这样的改进将会使冒泡排序短短六行就实现了

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {11,43,22,54,37,82,7};
        System.out.println(Arrays.toString(arr));

        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                if(arr[i] > arr[i+1]){
                    int temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }
            }
        }
        System.out.println("冒泡排序的结果为："+Arrays.toString(arr));
        System.out.println("======================");

    }

}