在之前的文章:排序算法——冒泡排序 中,我们描述了传统冒泡排序的过程及其实现,那么,有没有可以改进的地方呢,肯定是有的。假如在数组本身就已经排序好的情况下,或者经过一定的循环之后数组已经被排好了,此时接下来的循环就是在浪费时间,那么如何去解决

过程

这里引入一个变量isChange记录是否发生交换,如果未发生交换,说明数组已经被排好,此时即可结束循环。具体实现过程看下面代码,理解起来并不难。

Java实现

import java.util.Arrays;

public class BubbleSortImprove {
    public static void main(String[] args) {
        int[] a = new int[]{1, 2, 3, 4, 5, 6, 7, 8};
        System.out.println(Arrays.toString(sort(a)));
    }

    private static int[] sort(int[] a) {
        boolean isChange = false;
        for (int i = 0; i < a.length; i++) {
            isChange = false;
            for (int j = 0; j < a.length - i - 1; j++) {
                //相邻两项进行比较,若前大于后则交换位置
                if (a[j + 1] < a[j]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    isChange = true;//如果交换,则记录交换
                }
            }
            //如果未发生交换,说明排序完成
            if (!isChange) {
                break;
            }
        }
        return a;
    }
}
最后修改:2021 年 04 月 27 日 08 : 00 PM
如果觉得我的文章对你有用,请随意赞赏