java编程基础(三)冒泡排序

2020-10-26   99 次阅读


冒泡排序运算逻辑分析

冒泡

从上面的演示看到,排序运算主要依靠j向前递减来完成,j递减过程做两件事:

  1. 较小值向前移动
  2. 最小值移动到i位置

代码

package demo3;

import java.util.Arrays;
import java.util.Random;

public class Test1 {
    public static void main(String[] args) {
        int[] a = rnd();
        System.out.println(Arrays.toString(a));
        System.out.println("----------------------------");
        sort(a);
        System.out.println("----------------------------");
        System.out.println(Arrays.toString(a));
    }

    static void sort(int[] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = a.length-1; j > i; j--) {
                if (a[j-1]>a[j]) {
                    int t = a[j-1];
                    a[j-1] = a[j];
                    a[j] = t;
                }
            }
            System.out.println(Arrays.toString(a));
        }
    }

    static int[] rnd() {
        int[] a = new int[5 + new Random().nextInt(6)];

        for (int i = 0; i < a.length; i++) {
            a[i] = new Random().nextInt(100);
        }

        return a;
    }
}

冒泡排序优化

观察一下执行的结果:

冒泡

根据前面的演示,到蓝线位置就应该结束了,为什么i变量还在继续递增一直到末尾呢?我们能不能在排序已经完成的情况下让排序过程退出呢?

要判断排序已经完成是没有可以判断的条件的!没有条件我们就创造条件,继续看下面的演示:

冒泡

代码

只需要再增加三处代码,注意看注释编号1,2,3:

package demo3;

import java.util.Arrays;
import java.util.Random;

public class Test1 {
    public static void main(String[] args) {
        int[] a = rnd();
        System.out.println(Arrays.toString(a));
        System.out.println("----------------------------");
        sort(a);
        System.out.println("----------------------------");
        System.out.println(Arrays.toString(a));
    }

    static void sort(int[] a) {
        for (int i = 0; i < a.length; i++) {
            // 1. j开始之前设置flag的值
            boolean flag = false;

            for (int j = a.length-1; j > i; j--) {
                if (a[j-1]>a[j]) {
                    int t = a[j-1];
                    a[j-1] = a[j];
                    a[j] = t;
                    // 2. 有交换,flag 修改成 true
                    flag = true;
                }
            }

            // 3. j结束后检查 flag 的值
            if(! flag) {
                break; //排序完成,退出循环
            }
            System.out.println(Arrays.toString(a));
        }
    }

    static int[] rnd() {
        int[] a = new int[5 + new Random().nextInt(6)];

        for (int i = 0; i < a.length; i++) {
            a[i] = new Random().nextInt(100);
        }

        return a;
    }
}

代码仓库

https://gitee.com/benwang6/java-review

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

毕生所求无它,爱与自由而已