数据结构排序算法之冒泡排序详解(java实现)

  • Post author:
  • Post category:java


前言:

说起冒泡排序应该没有几个人不知道吧,今天来总结一下冒泡排序的知识。

知识点一:排序思想

冒泡排序:比较两个元素,如果不有序,则交换位置。每循环一次都会有某个元素放到恰到的位置。

另一种说法: 
       两两比较数据列表中的相邻的两项,满足条件,交换位置。每一轮循环中都会有一个元素放到指定的位置上,直到有序为止;

知识点二:冒泡排序算法分类

1,基础冒泡排序
2,改进冒泡排序
3,进一步改进的冒泡排序

说明:
   这里分类没有严格的意义,只是用来说明对冒泡排序改进的的一种说明。
   建议大家写冒泡排序使用3,相对来说效率高一下。

知识点三:时间复杂度,辅助空间、稳定性

时间复杂度:O(n^2)
辅助空间:O(1)
稳定性:稳定

知识点四:java实现

1.基础冒泡排序实现

    /**
     * 基础冒泡排序 (升序)
     */
    private void bubbleSort(int[] ints) {
        Objects.requireNonNull(ints);
        for (int i = 0; i < ints.length; i++) {
            //这里j要小于ints.length - 1,如果j < ints.length会报ArrayIndexOutOfBoundsException
            for (int j = 0; j < ints.length - 1; j++) {
                if (ints[j] > ints[j + 1]) {
                    int temp = ints[j];
                    ints[j] = ints[j + 1];
                    ints[j + 1] = temp;
                }
            }
        }
    }

测试类:

    @Test
    public void test() {
        int[] ints = {12, 5, 78, 99, 31, 8};
        bubbleSort(ints);

        Arrays.stream(ints).forEach(System.out::println);
    }

测试结果:

5
8
12
31
78
99

2.改进的冒泡排序

改进说明:
定义一个标识变量来标志一次循环中有没有交换位置,如果在一次循环中没有交换位置,此时说明数据集合中已经有序,直接跳出循环即可。 
这样可以避免内部循环多次判断,提高效率。
 /**
     * 改进冒泡排序 (升序)
     */
    private void bubbleSort1(int[] ints) {
        Objects.requireNonNull(ints);
        for (int i = 0; i < ints.length; i++) {
            //标志是否交换
            boolean flag = false;
            //这里j要小于ints.length - 1,如果j < ints.length会报ArrayIndexOutOfBoundsException
            for (int j = 0; j < ints.length - 1; j++) {
                if (ints[j] > ints[j + 1]) {
                    int temp = ints[j];
                    ints[j] = ints[j + 1];
                    ints[j + 1] = temp;
                    flag = true;
                }
            }
            //没有交换,说明现在已经是有序的,直接跳出循环
            if (!flag) {
                break;
            }
        }
    }

测试代码:

    @Test
    public void test() {
        int[] ints = {12, 5, 78, 99, 31, 8};
        //bubbleSort(ints);
        bubbleSort1(ints);
        //bubbleSort2(ints);
        Arrays.stream(ints).forEach(System.out::println);
    }

测试结果:

5
8
12
31
78
99

3.进一步改进的冒泡排序 (建议使用这个)

改进思想:
可以使用一个变量记录每次交换的最后位置,因为交换最后位置后面的元素都已经是有序的了,不需要在进行排序。默认交换的位置为数据集合的最后一个位置。
这样可以提高内部循环的效率,从而提高冒泡排序的整体效率。
 /**
     *  进一步改进的冒泡排序 (升序)
     * */
    private void bubbleSort2(int[] ints) {
        Objects.requireNonNull(ints);
        int lastSwap = ints.length - 1;
        for (int i = 0; i < ints.length; i++) {
            boolean flag = false;
            int m  = lastSwap;
            for (int j = 0; j < m; j++) {
                if (ints[j] > ints[j + 1]) {
                    int temp = ints[j];
                    ints[j] = ints[j + 1];
                    ints[j + 1] = temp;
                    flag = true;
                    lastSwap = j;
                }
            }
            if (!flag) {
                break;
            }
        }
    }

测试代码:

    @Test
    public void test() {
        int[] ints = {12, 5, 78, 99, 31, 8};
        //bubbleSort(ints);
        //bubbleSort1(ints);
        bubbleSort2(ints);
        Arrays.stream(ints).forEach(System.out::println);
    }

测试结果:

5
8
12
31
78
99

总结:

平时我们使用冒泡排序尽量使用我们改进过的,这样可以提高效率。



版权声明:本文为xinghuo0007原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。