-->

虫虫的技术博客 技术 生活

Monday, April 29, 2019

面试基础-冒泡排序

        多年的开发经验仍不能透彻理解一些基础的算法,按说懂个大概也行啊,言语稍微变通一下就可以啦,可更重要的是言语表达也是不在行,遇到一些姿态较高的,又爱跟你较真和抬扛的人的时候,就无奈了。想想算了吧,随他吧。可是你自己呢,别人看到的你仍是小白啊,那我就把自己当作小白,重新来过吧。
        没有系统的按照教科书的顺序,只按自己想到哪,学到哪,记录到哪。

下面进入正题,先来个冒泡排序。一个最简版本,一个稍微优化版本。

测试输入:new int[]{1, 17, 6, 9, 2, 4, 100, 38, 94, 29, 46, 3, 57, 65, 19, 5};


    /**
     * 最差的冒泡排序
     * n*(n-1)次比较,0-n*(n-1)次交换
     *
     * @param arr
     */
    public void sort0(int[] arr) {
        int compareTimes = 0;
        int swapTimes = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1; j++) {
                compareTimes++;
                if (arr[j] > arr[j + 1]) {
                    Util.swap(arr, j, j + 1);
                    swapTimes++;
                }
            }
        }
        System.out.println("数组长度:" + arr.length + " 比较次数:" + compareTimes + " 交换次数:" + swapTimes);
    }


打印输出:数组长度:16 比较次数:240 交换次数:46




    /**
     * 稍优化一点的冒泡排序
     * n*(n-1)/2次比较,(0-n*(n-1)/2)次交换
     *
     * @param arr
     */
    public void sort(int[] arr) {
        int compareTimes = 0;
        int swapTimes = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                compareTimes++;
                if (arr[j] > arr[j + 1]) {
                    swapTimes++;
                    Util.swap(arr, j, j + 1);
                }
            }
        }
        System.out.println("数组长度:" + arr.length + " 比较次数:" + compareTimes + " 交换次数:" + swapTimes);
    }



打印输出:数组长度:16 比较次数:120 交换次数:46

时间复杂度均为O(n^2)

code地址:https://github.com/angelala00/learn/blob/master/src/main/java/cn/jc/datastructure/sort/BubbleSort.java

1 comment:

Popular Posts

Copyright © 虫虫的成长历程 | Powered by Blogger Design by PWT | Blogger Theme by NewBloggerThemes.com