新手区 向高性能前进之 冒泡排序法优化

zailushang · 2017年02月09日 · 最后由 zailushang 回复于 2017年02月10日 · 39 次阅读

向高性能前进之 冒泡排序法😀

性能调优可以分为:硬件调优、网络调优、架构调优、组件配置调优、业务调优、数据库调优、代码调优等,此篇就是简单的代码调优实践

引用:马士兵老师的课程,以日期(年,月,日)数组为例,进行递增排序

优化效果

  • 日期数组元素为 1000 个时,原始冒泡法耗时 9 毫秒,改进后冒泡法耗时 4 毫秒,性能优化 55.55%;
  • 日期数组元素为 5000 个时,原始冒泡法耗时 162 毫秒,改进后冒泡法耗时 76 毫秒,性能优化 53.08%;
  • 日期数组元素为 1 万个时,原始冒泡法耗时 673 毫秒,改进后冒泡法耗时 299 毫秒,性能优化 55.57%;
  • 日期数组元素为 2 万个时,原始冒泡法耗时 2966 毫秒,改进后冒泡法耗时 1341 毫秒,性能优化 54.78%;
  • 日期数组元素为 3 万个时,原始冒泡法耗时 6928 毫秒,改进后冒泡法耗时 3157 毫秒,性能优化 54.43%;

综上所述:通过对冒泡法的改进后,当日期数组元素>=1000 时,性能优化了至少 50%。

冒泡法优化原理 --- 如下图

冒泡法优化原理图

原始冒泡法 --- 代码

public static void BubbleSort(DateArray[] d) {  //递增排序,普通冒泡法
    DateArray demo = new DateArray(2016,12,12);
    for(int i=0; i<d.length; i++) {
        for(int j=i+1; j<d.length; j++) {
            if(d[i].compare(d[j])>0) {
                demo = d[i];
                d[i] = d[j];
                d[j] = demo;
            }
        }
    }
}

改进后冒泡法 --- 代码

public static void BubbleSortGood(DateArray[] d) { //递增排序,改进冒泡法
    int z=0;
    DateArray demo = new DateArray(2016,12,12); 
    for(int i=0; i<d.length; i++) {
        z = i;
        for(int j=z+1; j<d.length; j++) {
            if(j < d.length) {
                if(d[z].compare(d[j])>0) {
                    z = j;
                }
            }else {
                demo = d[i];
                d[i] = d[j];
                d[j] = demo;
            }
        }
    }
}

测试源代码

public class TestDataSort {
    public static void main(String[] args) {
        long starttime_BubbleSort;  //原始冒泡法开始时间 变量定义
        long endtime_BubbleSort;    //原始冒泡法结束时间 变量定义
        long starttime_BubbleSortGood;  //改进冒泡法开始时间 变量定义
        long endtime_BubbleSortGood;    //改进冒泡法结束时间 变量定义

        //日期数据的定义及初始化
        DateArray[] d = new DateArray[1000];
        for(int i=0; i<d.length; i++) {
            d[i] = new DateArray((int)(2020+Math.random()*(2020-1990+1)),(int)(12+Math.random()*(12-1+1)),(int)(30+Math.random()*(30-1+1)));
        }

        //原始冒泡法计时及耗时输出
        starttime_BubbleSort = System.currentTimeMillis();
        BubbleSort(d);
        endtime_BubbleSort = System.currentTimeMillis();
        System.out.println("原始冒泡法耗时"+(long)(endtime_BubbleSort-starttime_BubbleSort)+"毫秒");

        System.out.println("----------------------------------------------");

        //改进冒泡法计时及耗时输出
        starttime_BubbleSortGood = System.currentTimeMillis();
        BubbleSortGood(d);
        endtime_BubbleSortGood = System.currentTimeMillis();        
        System.out.println("改进后冒泡法耗时"+(long)(endtime_BubbleSortGood-starttime_BubbleSortGood)+"毫秒");
    }

//递增排序,普通冒泡法
    public static void BubbleSort(DateArray[] d) {  
        DateArray demo = new DateArray(2016,12,12);
        for(int i=0; i<d.length; i++) {
            for(int j=i+1; j<d.length; j++) {
                if(d[i].compare(d[j])>0) {
                    demo = d[i];
                    d[i] = d[j];
                    d[j] = demo;
                }
            }
        }
    }

//递增排序,改进冒泡法
    public static void BubbleSortGood(DateArray[] d) { 
        int z=0;
        DateArray demo = new DateArray(2016,12,12); 
        for(int i=0; i<d.length; i++) {
            z = i;
            for(int j=z+1; j<d.length; j++) {
                if(j < d.length) {
                    if(d[z].compare(d[j])>0) {
                        z = j;
                    }
                }else {
                    demo = d[i];
                    d[i] = d[j];
                    d[j] = demo;
                }
            }
        }
    }

}

//日期数组类定义
class DateArray {
    int year;
    int month;
    int day;
    public DateArray(int year, int month, int day) {
        this.year = year;
        this.month = month;
        this.day = day;
    }
    public int compare(DateArray d) {
        return year > d.year ? 1
                : year < d.year ? -1
                : month > d.month ? 1
                : month < d.month ? -1
                : day > d.day ? 1
                : day < d.day ? -1
                        : 0;
    }

}
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
共收到 15 条回复 时间 点赞

你不对比下两个排序出来的结果吗?

已经对比了啊,下面的就是,文章中有了
日期数组元素为 1000 个时,原始冒泡法耗时 9 毫秒,改进后冒泡法耗时 4 毫秒,性能优化 55.55%;
日期数组元素为 5000 个时,原始冒泡法耗时 162 毫秒,改进后冒泡法耗时 76 毫秒,性能优化 53.08%;
日期数组元素为 1 万个时,原始冒泡法耗时 673 毫秒,改进后冒泡法耗时 299 毫秒,性能优化 55.57%;
日期数组元素为 2 万个时,原始冒泡法耗时 2966 毫秒,改进后冒泡法耗时 1341 毫秒,性能优化 54.78%;
日期数组元素为 3 万个时,原始冒泡法耗时 6928 毫秒,改进后冒泡法耗时 3157 毫秒,性能优化 54.43%;

#1 楼 @Lihuazhang 已经对比了啊,下面的就是,文章中有了
日期数组元素为 1000 个时,原始冒泡法耗时 9 毫秒,改进后冒泡法耗时 4 毫秒,性能优化 55.55%;
日期数组元素为 5000 个时,原始冒泡法耗时 162 毫秒,改进后冒泡法耗时 76 毫秒,性能优化 53.08%;
日期数组元素为 1 万个时,原始冒泡法耗时 673 毫秒,改进后冒泡法耗时 299 毫秒,性能优化 55.57%;
日期数组元素为 2 万个时,原始冒泡法耗时 2966 毫秒,改进后冒泡法耗时 1341 毫秒,性能优化 54.78%;
日期数组元素为 3 万个时,原始冒泡法耗时 6928 毫秒,改进后冒泡法耗时 3157 毫秒,性能优化 54.43%;

#3 楼 @zailushang 我的意思 是排序是否正确。。

#4 楼 @Lihuazhang 哦哦,这个验证过了,没问题,用 10 个元素左右的日期数据验证过了,没问题

#4 楼 @Lihuazhang 不过发现一个问题,就是咱们的文章阅读量其实是可以刷出来的

#6 楼 @zailushang 嗯,是可以的,刷一次记录一次

#7 楼 @Lihuazhang 那咱们的精华帖是怎么来评选的啊?

#8 楼 @zailushang 很多维度 不会即时评选. 社区的阅读数不做参考. 以 ga 的统计为准.

看了下,貌似是空间换取时间,原来是比较的同时不断替换,现在是比较的时候用中间变量 z 记录比较得出的较大值,确认所有数字都比较过后再进行替换。

相比原始的性能优化是比较明显,赋值次数减少了很多。不过看起来有点像选择排序法。

PS:你这种测试方法不大对吧,排序算法的效率提升评估不应该纯粹增大数据量吧,应该还要考虑最好情况(本来就排好序)和最坏情况(例如本来是倒序的)下的算法性能差距吧。或者用算法的时间和空间复杂度进行比较。

#10 楼 @chenhengjie123 是的,同意,所以在新手区,我还是新手,多谢指导

#11 楼 @zailushang 哈哈,指导说不上,相互交流而已。期待你更多的分享~

在最外层 for 的时候加下判断,如果你的 j 的这一层没有交换操作,直接跳出循环,可节省一部分时间

#13 楼 @zoo4778362 为什么要跳出循环啊,没有明白

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册