原 java冒泡算法和优化

版权声明：本文为博主原创文章，请尊重他人的劳动成果，转载请附上原文出处链接和本声明。
本文链接：https://www.91mszl.com/zhangwuji/article/details/1327

一：冒泡算法的介绍。

1.1）介绍：冒泡排序是通过两两比较，将数据当中最大的那个“浮”到数列的顶端，通过这种不断的上“浮”，最终达到有序的排序算法。冒泡排序因其简单稳定而受到大家的欢迎，也是初学者最容易掌握的一种排序算法。

1.2）稳定性：冒泡排序就是把大的元素往后调（或者小的元素往前调）。比较的是相邻的两个元素，交换也只发生在这两个元素之间。所以，如果两个元素相等，是不会交换的；即使两个元素相等却没有相邻，那么通过前面的两两交换把他们相邻起来，这时候比较的相等也是不会交换的，因此相同元素的前后顺序不会改变，所以冒泡排序是一种稳定排序算法。

1.3）时间复杂度：假设数据有n条，那么需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(i表示循环第几次，1≤i≤n-1)，在这种情况下，比较次数为n（n-1）/2，即O(n²)。所以时间复杂度为O(n²)。

1.4）冒泡排序优点：比较简单，空间复杂度较低，是稳定的算法。

1.5）冒泡排序缺点：因其每次只能移动相邻两个数据，所以时间复杂度高，效率低。当处理大量数据排序时，效率低下这一特点非常明显。

二：代码演示。

2.1）常规写法。

// 常规写法
public static int[] bubble(int[] arrays){
    for(int i=0; i<arrays.length-1; i++){ // 循环趟数
        for(int k=0; k<arrays.length-1 - i; k++){ // 循环次数:冒泡算法每循环一趟会找出一个最大的数，所以每次循环减少一次
            if(arrays[k] > arrays[k+1]){
                int tmp=arrays[k];
                arrays[k]=arrays[k+1];
                arrays[k+1]=tmp;
            }
        }
    }
    return arrays;
}

public static void main(String[] args) {
    int arrays[] = {3, 1, 8, 15, 11, 7};
    int[] result=bubble(arrays);

    for(int h=0; h<result.length; h++){
        System.out.println("最终的排序结果：" + result[h]);
    }
}

执行结果：

最终的排序结果：1
最终的排序结果：3
最终的排序结果：7
最终的排序结果：8
最终的排序结果：11
最终的排序结果：15

2.2）优化一。

我们假设一种场景，假设我们的数组是如1, 2, 3, 4, 7, 6 或 8, 2, 3, 4, 6, 7 经过第一轮排序就可以将数组排列好，此时我们应该无须在进行排序，也即不需要在将大的数据向后调。我们可以设置一个标志，如果代码执行了内循环则表示还有需要交换的数据，如果没有则表示数组已经不需要在进行交换。

// 优化一
public static int[] bubble1(int[] arrays){
    boolean flag=true; // 设立一个标志，判断当前数据是否有序，默认为有序

    for(int i=0; i<arrays.length-1; i++){ // 循环趟数
        for(int k=0; k<arrays.length-1 - i; k++){ // 循环次数:冒泡算法每循环一趟会找出一个最大的数，所以每次循环减少一次
            if(arrays[k] > arrays[k+1]){
                int tmp=arrays[k];
                arrays[k]=arrays[k+1];
                arrays[k+1]=tmp;
                flag=false;
            }
        }

        if(flag){
            return arrays;
        }
        flag = true; // 如果还处于无序状态，将标志复原
    }
    return arrays;
}

public static void main(String[] args) {
    int arrays[] = {9, 1, 2, 3, 4, 5, 6, 7, 8};
    int[] result=bubble1(arrays);

    for(int h=0; h<result.length; h++){
        System.out.println("最终的排序结果：" + result[h]);
    }
}

执行结果：

最终的排序结果：1
最终的排序结果：2
最终的排序结果：3
最终的排序结果：4
最终的排序结果：5
最终的排序结果：6
最终的排序结果：7
最终的排序结果：8
最终的排序结果：9

2.3）优化二。

我们优化完后，有发现了新的问题，我们的数组是3, 2, 1, 4, 5, 6, 7, 8 

我们发现第一轮排序结果为：2, 1, 3, 4, 5, 6, 7, 8

我们发现第二轮排序结果为：1, 2, 3, 4, 5, 6, 7, 8

4,5,6,7,8这部分是有序的，当第二轮排序后，2已经不需要在和3,4,5,6,7,8进行比较了。我们设立标志位来记录最后一次交换的位置，下次冒泡时这个标志以后的数据就不需要在冒泡了。

// 优化二
public static int[] bubble2(int[] arrays){
    boolean flag=true; // 设立一个标志，判断当前数据是否有序，默认为有序
    int lastLocation=arrays.length-1; // 标志，用于记录最后交换的位置。初始值是最后一位

    for(int i=0; i<arrays.length-1; i++){ // 循环趟数
        int nowLocation=0; // 临时标志，最后一次交换之前还有多次交换，这些并不是我们想要的。我们通过最后的覆盖之前的这种方式得到最后的标志位
        for(int k=0; k<lastLocation; k++){ // //标志位之后的数据已经有序，之前是固定的length-i-1，现在是可变的不确定的
            if(arrays[k] > arrays[k+1]){
                int tmp=arrays[k];
                arrays[k]=arrays[k+1];
                arrays[k+1]=tmp;
                flag=false;
                nowLocation=k; // 交换后将位置告诉临时标志
            }
        }

        lastLocation=nowLocation; // 临时标志将最后的位置告诉标志位
        if(flag){
            return arrays;
        }
        flag = true; // 如果还处于无序状态，将标志复原
    }
    return arrays;
}

public static void main(String[] args) {
    int arrays[] = {3, 2, 1, 4, 5, 6, 7, 8};
    int[] result=bubble2(arrays);

    for(int h=0; h<result.length; h++){
        System.out.println("最终的排序结果：" + result[h]);
    }
}

2.4）优化三。

终极优化，我们争对这种数组的情况进行优化。1, 2, 3, 4, 5, 6, 7, 8, 9, 0 如果没有优化，数据要一次次的冒泡，移动到0的右边。这样效率非常的低。我们采用双向冒泡的方法。从前向后冒泡，在从后向前冒泡，将最小的移动到最前面。

// 优化三
public static int[] bubble3(int[] arrays){
    boolean flag=true;
    int newLocation=0; // 记录前面最小的已经有序的数据个数
    int lastLocation=arrays.length-1; // 标志，用于记录最后交换的位置。初始值是最后一位。

    for (int i=0; i<arrays.length-1; i++) {
        int nowLocation=0; // 临时标志，最后一次交换之前还有多次交换，这些并不是我们想要的。我们通过最后的覆盖之前的这种方式得到最后的标志位。
        for (int k = 0; k<lastLocation; k++) { // 标志位之后的数据已经有序，之前是固定的length-i-1，现在是可变的不确定的。
            if (arrays[k] > arrays[k+1]) {
                int temp=arrays[k];
                arrays[k]=arrays[k+1];
                arrays[k+1]=temp;
                flag = false;
                nowLocation=k; // 交换后将位置告诉临时标志
            }
        }

        lastLocation = nowLocation; // 临时标志将最后的位置告诉标志位
        if (flag) {
            return arrays;
        }

        for (int k=lastLocation; k>newLocation; k--){ // 从后向前冒泡，找出最小的。原理同上面代码
            int tmp = arrays[k];
            arrays[k] = arrays[k - 1];
            arrays[k - 1] = tmp;
            flag = false;
        }
        newLocation++;
        if (flag){
            return arrays;
        }
    }
    return arrays;
}

public static void main(String[] args) {
    int arrays[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
    int[] result=bubble3(arrays);

    for(int h=0; h<result.length; h++){
        System.out.println("最终的排序结果：" + result[h]);
    }
}

执行结果：

最终的排序结果：0
最终的排序结果：1
最终的排序结果：2
最终的排序结果：3
最终的排序结果：4
最终的排序结果：5
最终的排序结果：6
最终的排序结果：7
最终的排序结果：8
最终的排序结果：9

参考资料：

https://blog.csdn.net/qq_39188747/article/details/88266386

https://www.cnblogs.com/jyroy/p/11248691.html#idx_7