经典再现,回顾常见排序算法之冒泡排序,附Java源码及优化改进实现

时间:2024-07-15 09:31:20

回顾一下排序算法,老酒装新瓶,给自己的技能点做个回放。

排序(Sorting) 是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个有序的序列,也可以理解为高矮个站队。

衡量排序算法的两个指标,时间复杂度 和 稳定性。

举个例子,如果我们的数据是:3 5 4 2 2, 稳定的排序最后的俩个2在排好序后他们的原始前后顺序是不会变的(第一个2还在第二个2的前面,有点绕,你可以理解为小明和小强一样高,最开始小明在小强的前面,排完序之后,小明还在小强前面,就属于稳定的排序),不稳定的排序最后两个2的顺序可能交换(也就是可能小明在前,也可能小强在前)。

时间复杂度先跳过哈,我回头单独写一篇文章介绍,本文主要介绍和实操“冒泡排序”。

介绍

冒泡排序是將比較大的數字移到序列的后面,较小的移到前面。

从第一个开始,第一个和第二个比,谁高(大)谁站后面(两个人(数)的位置交换,不是最后面),当前第二个再与第三个比,依次进行,一轮下来之后,筛选出来最高个(大)的人(数)。

上面就表示第一轮结束了,第二轮和第一轮一样,只是最后一个人(数)已经排好了,不用管他了。

经过 N-1 轮之后,排序完成。

N 个人,经过 N-1 轮,相当于 N*(N-1)=N^2-N, 时间复杂度取最大的 O(n^2)

实例

原始数据:

3 5 2 6 2

第一轮

比较 3 和 5,5 大于 3 ,不需交换

3 5 2 6 2

继续比较 5 和 2,5 大于 2,交换位置

3 2 5 6 2

继续比较 5 和 6,6 大于 5,不需交换

3 2 5 6 2

继续比较 6 和 2,6 大于 2,交换位置

3 2 5 2 6

6 移到最后,两个2都分别向前移动。

第二轮

比较 3 和 2, 3 大于 2,交换位置

2 3 5 2 6

比较 3 和 5, 5 大于 3,不需交换

2 3 5 2 6

比较 5 和 2, 5 大于 2,交换位置

2 3 2 5 6

不需比较 5 和 6

第三轮

比较 2 和 3, 3 大于 2,不需交换

2 3 2 5 6

比较 3 和 2, 3 大于 2,交换位置

2 2 3 5 6

不需比较了

第四轮

比较 2 和 2,不需交换

2 2 3 5 6

四轮结束,最终的结果:

2 2 3 5 6

Java 实现

public class Bubble {

    /**
     * 冒泡排序
     */
    public static int[] sort(int[] array) {
        int temp;
        // 第一层循环表明比较的轮数, 比如 length 个元素,比较轮数为 length-1 次(不需和自己比)
        for (int i = 0; i < array.length - 1; i++) {
            System.out.println("第" + (i + 1) + "轮开始");
            // 第二层循环,每相邻的两个比较一次,次数随着轮数的增加不断减少,每轮确定一个最大的,不需比较那个最大的
            for (int j = 0; j < array.length - 1 - i; j++) {
                System.out.println("第" + (i + 1) + "轮,第" + (j + 1) + "次比较:");
                if (array[j + 1] < array[j]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
                for (int k : array) {
                    System.out.print(k + " ");
                }
                System.out.println();
            }
            System.out.println("结果:");
            for (int k : array) {
                System.out.print(k + " ");
            }
            System.out.println();
        }
        return array;
    }

    public static void main(String[] args) {
        int[] array = {3, 5, 2, 6, 2};
        int[] sorted = sort(array);
        System.out.println("最终结果");
        for (int i : sorted) {
            System.out.print(i + " ");
        }
    }

}

输出结果:

第1轮开始
第1轮,第1次比较:
3 5 2 6 2 
第1轮,第2次比较:
3 2 5 6 2 
第1轮,第3次比较:
3 2 5 6 2 
第1轮,第4次比较:
3 2 5 2 6 
结果:
3 2 5 2 6 
第2轮开始
第2轮,第1次比较:
2 3 5 2 6 
第2轮,第2次比较:
2 3 5 2 6 
第2轮,第3次比较:
2 3 2 5 6 
结果:
2 3 2 5 6 
第3轮开始
第3轮,第1次比较:
2 3 2 5 6 
第3轮,第2次比较:
2 2 3 5 6 
结果:
2 2 3 5 6 
第4轮开始
第4轮,第1次比较:
2 2 3 5 6 
结果:
2 2 3 5 6 
最终结果
2 2 3 5 6 

优化改进

对冒泡排序常见的改进方法是加入一标志性变量 pos ,用于标志某一趟排序过程中是否有数据交换,如果进行某一趟排序时并没有进行数据交换(都不需要交换,肯定排好了),则说明数据已经按要求排列好,可立即结束排序,避免不必要的比较过程。

设置一标志性变量 pos,用于记录每趟排序中最后一次进行交换的位置(后面有多个没有发生交换,说明后面已经排好了)。由于 pos 位置之后的记录均已交换到位,故在进行下一趟排序时只要排到 pos 位置即可。

怎么理解呢?

3 2 4 5 6 为例

第一轮排序,发生交换的位置仅仅是 3 和 2, 则 pos 是 0(索引位置从0开始)

直接一轮就结束了,而不用傻傻的再跑4轮。

代码实现:

public class Bubble {


    /**
     * 冒泡排序(优化改进版)
     */
    public static int[] sort(int[] array) {
        int temp;
        int time = 1;
        for (int i = array.length - 1; i > 0; ) {
            System.out.println("第" + time + "轮开始");
            int pos = 0;
            // 第二层循环,每相邻的两个比较一次,次数随着轮数的增加不断减少,每轮确定一个最大的,不需比较那个最大的
            for (int j = 0; j < i; j++) {
                System.out.println("第" + time + "轮,第" + (j + 1) + "次比较:");
                if (array[j + 1] < array[j]) {
                    // 记录最后一次交换位置的索引,下一轮只需排序到 pos 位置
                    pos = j;
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
                for (int k : array) {
                    System.out.print(k + " ");
                }
                System.out.println();
            }
            // 之前是 i--, 优化后直接跳到最后交换位置的索引
            i = pos;
            time++;
            System.out.println("结果:");
            for (int k : array) {
                System.out.print(k + " ");
            }
            System.out.println();
        }
        return array;
    }

    public static void main(String[] args) {
        int[] array = {3, 2, 4, 5, 6};
        int[] sorted = sort(array);
        System.out.println("最终结果");
        for (int i : sorted) {
            System.out.print(i + " ");
        }
    }

}

结果输出:

第1轮开始
第1轮,第1次比较:
2 3 4 5 6 
第1轮,第2次比较:
2 3 4 5 6 
第1轮,第3次比较:
2 3 4 5 6 
第1轮,第4次比较:
2 3 4 5 6 
结果:
2 3 4 5 6 
最终结果
2 3 4 5 6 

总结

好了,今天的分享就这些,关于冒泡排序,你学会了嘛?如果学会了,看懂了,请留下你的点赞,收藏,分享,关注。

有任何问题可以公作号:新质程序猿,可以找到我。