当前位置: 主页 > JAVA语言

java 冒泡排序-排序冒泡排序法

发布时间:2023-03-24 07:05   浏览次数:次   作者:佚名

**算法描述**

1. 依次比较数组中相邻两个元素大小java 冒泡排序,若 a[j] > a[j+1],则交换两个元素,两两都比较一遍称为一轮冒泡java 冒泡排序,结果是让最大的元素排至最后

2. 重复以上步骤,直到整个数组有序

根据描述,第一轮冒泡代码:数组共有8个元素,需要比较7次

    public static void main(String[] args) {
        int[] a = {5, 9, 7, 4, 1, 3, 2, 8};
        // 一轮冒泡
        for (int i = 0; i < a.length - 1; i++) {
            System.out.println("比较次数:" + i);
            if (a[i] > a[i + 1]) {
                swap(a, i, i + 1);
            }
        }
        System.out.println("第一轮:" + Arrays.toString(a));
    }
    public static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    控制台输出:
    比较次数0
    比较次数1
    比较次数2
    比较次数3
    比较次数4
    比较次数5
    比较次数6
    第一轮:[5, 7, 4, 1, 3, 2, 8, 9]

外层加上比较轮数

    public static void main(String[] args) {
        int[] a = {5, 9, 7, 4, 1, 3, 2, 8};
        for (int k=0;k a[i + 1]) {
                    swap(a, i, i + 1);
                }
            }
            System.out.println("第"+ k +"轮:" + Arrays.toString(a));
        }
    }
    public static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
控制台输出:
第0轮冒泡
比较次数:0
比较次数:1
比较次数:2
比较次数:3
比较次数:4
比较次数:5
比较次数:6
第0轮:[5, 7, 4, 1, 3, 2, 8, 9]
第1轮冒泡
比较次数:0
比较次数:1
比较次数:2
比较次数:3
比较次数:4
比较次数:5
比较次数:6
第1轮:[5, 4, 1, 3, 2, 7, 8, 9]
第2轮冒泡
比较次数:0
比较次数:1
比较次数:2
比较次数:3
比较次数:4
比较次数:5
比较次数:6
第2轮:[4, 1, 3, 2, 5, 7, 8, 9]
第3轮冒泡
比较次数:0
比较次数:1
比较次数:2
比较次数:3
比较次数:4
比较次数:5
比较次数:6
第3轮:[1, 3, 2, 4, 5, 7, 8, 9]
第4轮冒泡
比较次数:0
比较次数:1
比较次数:2
比较次数:3
比较次数:4
比较次数:5
比较次数:6
第4轮:[1, 2, 3, 4, 5, 7, 8, 9]
第5轮冒泡
比较次数:0
比较次数:1
比较次数:2
比较次数:3
比较次数:4
比较次数:5
比较次数:6
第5轮:[1, 2, 3, 4, 5, 7, 8, 9]
第6轮冒泡
比较次数:0
比较次数:1
比较次数:2
比较次数:3
比较次数:4
比较次数:5
比较次数:6
第6轮:[1, 2, 3, 4, 5, 7, 8, 9]
 

排序优化1

发现每轮冒泡的比较次数都是7次,实际上,第一轮冒泡排序后,9到了最右侧,第二轮冒泡排序只需要比较6次,第三轮冒泡再少1次,只需比较5次。。。

改进一下代码,随着比较轮数的增加,每轮比较次数减少

    public static void main(String[] args) {
        int[] a = {5, 9, 7, 4, 1, 3, 2, 8};
        for (int k=0;k a[i + 1]) {
                    swap(a, i, i + 1);
                }
            }
            System.out.println("第"+ k +"轮:" + Arrays.toString(a));
        }
    }
    public static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
控制台输出:
第0轮冒泡
比较次数:0
比较次数:1
比较次数:2
比较次数:3
比较次数:4
比较次数:5
比较次数:6
第0轮:[5, 7, 4, 1, 3, 2, 8, 9]
第1轮冒泡
比较次数:0
比较次数:1
比较次数:2
比较次数:3
比较次数:4
比较次数:5
第1轮:[5, 4, 1, 3, 2, 7, 8, 9]
第2轮冒泡
比较次数:0
比较次数:1
比较次数:2
比较次数:3
比较次数:4
第2轮:[4, 1, 3, 2, 5, 7, 8, 9]
第3轮冒泡
比较次数:0
比较次数:1
比较次数:2
比较次数:3
第3轮:[1, 3, 2, 4, 5, 7, 8, 9]
第4轮冒泡
比较次数:0
比较次数:1
比较次数:2
第4轮:[1, 2, 3, 4, 5, 7, 8, 9]
第5轮冒泡
比较次数:0
比较次数:1
第5轮:[1, 2, 3, 4, 5, 7, 8, 9]
第6轮冒泡
比较次数:0
第6轮:[1, 2, 3, 4, 5, 7, 8, 9]

查看控制台输出,在第4轮冒泡排序后,数组已经有序了,就没有必要再进行第5、第6轮排序,

如何减少不必要的冒泡次数?

当某一轮的冒泡排序没有发生交换,那就说明,整个数组已经有序了

改进代码

    public static void main(String[] args) {
        int[] a = {5, 9, 7, 4, 1, 3, 2, 8};
        for (int k=0;k a[i + 1]) {
                    swap(a, i, i + 1);
                    swapped = true;
                }
            }
            System.out.println("第"+ k +"轮:" + Arrays.toString(a));
            if (!swapped) {
                break;
            }
        }
    }
    public static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
控制台输出:
第0轮冒泡
比较次数:0
比较次数:1
比较次数:2
比较次数:3
比较次数:4
比较次数:5
比较次数:6
第0轮:[5, 7, 4, 1, 3, 2, 8, 9]
第1轮冒泡
比较次数:0
比较次数:1
比较次数:2
比较次数:3
比较次数:4
比较次数:5
第1轮:[5, 4, 1, 3, 2, 7, 8, 9]
第2轮冒泡
比较次数:0
比较次数:1
比较次数:2
比较次数:3
比较次数:4
第2轮:[4, 1, 3, 2, 5, 7, 8, 9]
第3轮冒泡
比较次数:0
比较次数:1
比较次数:2
比较次数:3
第3轮:[1, 3, 2, 4, 5, 7, 8, 9]
第4轮冒泡
比较次数:0
比较次数:1
比较次数:2
第4轮:[1, 2, 3, 4, 5, 7, 8, 9]
第5轮冒泡
比较次数:0
比较次数:1
第5轮:[1, 2, 3, 4, 5, 7, 8, 9]

查看控制台,发现少了第6轮冒泡;在第4轮的时候,3、2交换位置,在第5轮的时候,发现没有进行交换,退出循环

换个有序数组,效果更明显

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, 7, 8, 9};
        for (int k=0;k a[i + 1]) {
                    swap(a, i, i + 1);
                    swapped = true;
                }
            }
            System.out.println("第"+ k +"轮:" + Arrays.toString(a));
            if (!swapped) {
                break;
            }
        }
    }
    public static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
控制台输出:
第0轮冒泡
比较次数:0
比较次数:1
比较次数:2
比较次数:3
比较次数:4
比较次数:5
比较次数:6
第0轮:[1, 2, 3, 4, 5, 7, 8, 9]

查看控制台,比较了7次,但是未发生交换,对于有序数组,经过一轮冒泡即可确定其为有序数组

* 优化点1:每经过一轮冒泡,内层循环就可以减少一次

* 优化点2:如果某一轮冒泡没有发生交换,则表示所有数据有序,可以结束外层循环

排序优化2

记录下来,每轮比较,最后一次交换位置的数组索引

    public static void main(String[] args) {
        int[] a = {5, 9, 7, 4, 1, 3, 2, 8};
        int n = a.length - 1;
        for (int k = 0; k < a.length - 1; k++) {
            System.out.println("第" + k + "轮冒泡");
            int last = 0; // 表示最后一次交换索引位置
            for (int i = 0; i < n; i++) {
                System.out.println("比较次数" + i);
                if (a[i] > a[i + 1]) {
                    swap(a, i, i + 1);
                    last = i;
                }
            }
            n = last;
            System.out.println("第" + k + "轮冒泡" + Arrays.toString(a));
            if (n == 0) {
                break;
            }
        }
    }
    public static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
控制台输出:
第0轮冒泡
比较次数0
比较次数1
比较次数2
比较次数3
比较次数4
比较次数5
比较次数6
第0轮冒泡[5, 7, 4, 1, 3, 2, 8, 9]
第1轮冒泡
比较次数0
比较次数1
比较次数2
比较次数3
比较次数4
比较次数5
第1轮冒泡[5, 4, 1, 3, 2, 7, 8, 9]
第2轮冒泡
比较次数0
比较次数1
比较次数2
比较次数3
第2轮冒泡[4, 1, 3, 2, 5, 7, 8, 9]
第3轮冒泡
比较次数0
比较次数1
比较次数2
第3轮冒泡[1, 3, 2, 4, 5, 7, 8, 9]
第4轮冒泡
比较次数0
比较次数1
第4轮冒泡[1, 2, 3, 4, 5, 7, 8, 9]
第5轮冒泡
比较次数0
第5轮冒泡[1, 2, 3, 4, 5, 7, 8, 9]

* 优化点:每轮冒泡时,最后一次交换索引可以作为下一轮冒泡的比较次数,如果这个值为零,表示整个数组有序,直接退出外层循环即可