冒泡排序实现与性能优化及JDK排序类分享

开心一笑

【我现在出门都得带口罩，要不然就嗓子疼还咳嗽，想吸一口新鲜空气真的是太难了，估计以后纯净的空气得比红酒还值钱啊。那些有钱人出门都得背个空气瓶，见面就问：哎呦，王总啊，你的是几几年的空气啊？王总：“啊，我吸的是80年的”。我：“哦，那我比你强啊，我吸的是93年的”。王总：“哦，那，你那味咋样啊？”。我：“还行吧，要不你吸一口我这，尝尝”。所以说好好珍惜呼吸的机会吧。估计以后连喘气都费劲。】

唯美泡泡

提出问题

java中的冒泡排序以及JDK其他排序类学习???

解决问题

1.冒泡排序的简单介绍

8大经典算法中的经典的一个，可以实现对数组值得排序。小的值就像泡泡一样，在排序中不断的冒到顶端。网上有很多这方面的介绍，不多说。

2.冒泡排序Java实现

网上冒泡排序算法很多。冒泡排序在工作中，说实话用的比较少。但是，在面试中经常会问到。

package com.evada.de;
import org.junit.Test;
/**
 * @Author 阿毅
 * Created by Ay on 2016/01/21.
 */
public class Ay{
    @Test
    public void test(int[] arr){
        // int [] arr = {3,2,1,4,5};
        //定义临时变量
        int temp;
        //外层循环次数：总长度（arr.length） - 1
        for(int i=0;i<arr.length-1;i++){
            //外层每循环一次，内层循环依次减 1
            for(int j=0;j<arr.length-i-1;j++){
                if(arr[j+1]<arr[j]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
}

3.冒泡排序的性能分析和算法优化（外层循环优化）

对于这样的数组[2,1,3,4,5,6,7]，冒泡排序经过第一轮，已经变成有序的了，但是的冒泡还是要继续进行没有营养的两两比较，从而牺牲了时间。

由于冒泡排序的时间复杂度为O(n*n)。所以，当数据越多的时候越慢，非常不适合大数据的排序，所以我们测试的时候也是用的长度为800的随机数组。

解决方法：如果用一个flag来判断一下，当前数组是否已经有序，如果有序就退出循环，这样可以明显的提高冒泡排序的性能。

Java代码实现

package com.evada.de;
import org.junit.Test;
import java.util.*;
/**
 * @Author 阿毅
 * Created by Ay on 2016/01/21.
 */
public class Ay{
    @Test
    public void test(){
        boolean flag = true;
        int [] arr = {3,2,1,4,5};
        //定义临时变量
        int temp;
        //冒泡趟数，n-1趟
        for(int i=0;i<arr.length-1;i++){
            for(int j=0;j<arr.length-i-1;j++){
                if(arr[j+1]<arr[j]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = true;
                }
            }
            if(!flag){
                break;//若果没有发生交换，则退出循环
            }
        }

        System.out.println(Arrays.toString(arr));
    }
}

4.冒泡排序第二种优化（内层循环优化）

记住最后一次交换发生位置的冒泡排序

package com.evada.de;
import org.junit.Test;
/**
 * @Author 阿毅
 * Created by Ay on 2016/01/21.
 */
public class Ay{
    @Test
    public void test(int[] arr){
        int i = 0, j = 0;
        //pos变量用来标记循环里最后一次交换的位置
        int k = arr.length - 1,pos = 0;
        //一共要排序size-1次
        for (i = 0; i < arr.length - 1; i++){
            //每次遍历标志位都要先置为0，才能判断后面的元素是否发生了交换
            int flag = 0;
            //选出该趟排序的最大值往后移动
            for (j = 0; j <k; j++){
                if (arr[j] > arr[j + 1]){
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    //只要有发生了交换，flag就置为1
                    flag = 1;
                    //循环里最后一次交换的位置 j 赋给pos
                    pos = j;
                }
            }
            k = pos;
            //判断标志位是否为0，如果为0，说明后面的元素已经有序，就直接return
            if (flag == 0){
                return;
            }
        }
    }
}

5.JDK基本类型数组排序Arrays.sort

package com.evada.de;
import org.junit.Test;
import java.util.Arrays;
/**
 * @Author 阿毅
 * Created by Ay on 2016/01/21.
 */
public class Ay{
    @Test
    public void test(){
        // 数组初始化
        int[] a = { 3, 5, 2, 1, 8, 6, 9, 4, 0};
        // 排序
        Arrays.sort(a);
        // 输出排序之后的结果
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}

6.JDK中Collections.sort()实现排序第一种

第一种是list中的对象实现Comparable接口：

package com.evada.de;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
 * @Author 阿毅
 * Created by Ay on 2016/01/21.
 */
public class Ay{
    @Test
    public void test(){
        User user1 = new User();
        user1.setName("a");
        user1.setOrder(1);
        User user2 = new User();
        user2.setName("b");
        user2.setOrder(2);
        List<User> list = new ArrayList<>();
        list.add(user2);
        list.add(user1);
        Collections.sort(list);
        for(User user : list){
            System.out.println(user.getName());
        }
    }

    /**
     * 根据order对User排序
     */
     class User implements Comparable<User>{
        private String name;
        private Integer order;
        public String getName() {
            return name;
        }
        public void setName(String name) {
            this.name = name;
        }
        public Integer getOrder() {
            return order;
        }
        public void setOrder(Integer order) {
            this.order = order;
        }
        public int compareTo(User arg0) {
            return this.getOrder().compareTo(arg0.getOrder());
        }
    }
}

7.JDK中Collections.sort()实现排序第二种

第二种方法是根据Collections.sort重载方法来实现：

package com.evada.de;
import org.junit.Test;
import java.util.*;
/**
 * @Author 阿毅
 * Created by Ay on 2016/01/21.
 */
public class Ay{
    @Test
    public void test(){
        User user1 = new User();
        user1.setName("a");
        user1.setPrice(11);
        User user2 = new User();
        user2.setName("b");
        user2.setPrice(2);
        Set<User> Hset = new HashSet<>();
        Hset.add(user2);
        Hset.add(user1);
        List<User> list = new ArrayList<>();
        list.addAll(Hset);
        Collections.sort(list,new Comparator<User>(){
            public int compare(User arg0, User arg1) {
                //升序
                return arg0.getPrice().compareTo(arg1.getPrice());
            }
        });
        for(User u : list){
            System.out.println(u.getName());
        }
    }

    /**
     * 根据order对User排序,无需实现Comparable接口
     */
    class User {
        private String name;
        private Integer order;
        private Integer price;
        public Integer getPrice() {
            return price;
        }
        public void setPrice(Integer price) {
            this.price = price;
        }
        public String getName() {
            return name;
        }
        public void setName(String name) {
            this.name = name;
        }
        public Integer getOrder() {
            return order;
        }
        public void setOrder(Integer order) {
            this.order = order;
        }
    }
}

读书感悟

来自近藤麻理惠《怦然心动的人生整理魔法》

  • 所谓整理，就是整理每一件物品的"过去"。
  • 一旦把东西放进袋子里，就不会再使用了。
  • 说的夸张一点，生而为人，对"什么能让自己心动"的判断是了解自己到底是一个怎样的人的重要线索。
  • 如果是男女共用衣柜的情况，我的建议是男士的衣服放在上层，女士的衣服放在下层。摆放鞋子的时候，不管是男鞋还是女鞋都含有"支撑的基础"的意思，性质相同。所以，只需简单地把体积大、分量重的男鞋放在下层，女鞋放在上层就能保持平衡。
  • 并不是"这个也扔，那个也扔"，而是"有选择地留下发光的东西，这才是理想生活的开端"。
  • 无论丢弃物品还是拥有物品，都是为了让自己幸福。
  • 教孩子折衣服，有助于培养他的整理习惯。
  • 对有心动感的物品判断速度会很快，拿着物品的手指很柔软，看着物品的眼睛会闪闪发光。如果拿着没有心动感的物品，则双手会瞬间停止动作，还会摇头皱眉地作思考状，最后还会漫不经心地把物品扔到"留存处"。
  • 为了珍惜真正富有价值的物品，必须首先丢弃已经完成了使命的物品。
  • 真正的必需品肯定是能让自己幸福的东西，所以，应该积极地把必需品当作"心动物品"来对待。
  • 凡是不符合"现在正使用""暂且需要""需要永存"这三项标准的文件，都应该毫不犹豫地全部丢掉。
  • 珍惜物品，从某种程度上来说也是珍惜自己的一种表现。

经典故事

【一个佛陀在旅途中，碰到一个不喜欢他的人。连续好几天，好长一段路，那人用尽各种方法污蔑他。最后，佛陀转身问那人："若有人送你一份礼物，但你拒绝接受，那么这份礼物属于谁呢？"那人回答："属于原本送礼的那个人。"佛陀笑着说："没错。若我不接受你的谩骂，那你就是在骂自己？"那人摸摸鼻子走了。
启发：只要心灵健康，别人怎么想都影响不了我们。若我们一味地在乎别人的想法或说法，就会失去自主权。】

大神文章

【1】java实现冒泡排序
【2】冒泡排序优化版,性能近乎翻倍
【3】黑马程序员——冒泡排序的优化和选择排序
【4】冒泡排序算法及其两种优化
【5】Java中排序总结
【6】JDK7中的排序算法详解--Collections.sort和Arrays.sort
【7】JDK1.7 Collections.sort Arrays.sort发现的问题
【8】java List 排序 Collections.sort()

唯美泡泡

其他

如果有带给你一丝丝小快乐，就让快乐继续传递下去，欢迎点赞、顶、欢迎留下宝贵的意见、多谢支持！

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 194,242评论 5赞 459
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 81,769评论 2赞 371
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 141,484评论 0赞 319
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,133评论 1赞 263
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 61,007评论 4赞 355
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,080评论 1赞 272
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,496评论 3赞 381
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,190评论 0赞 253
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,464评论 1赞 290
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,549评论 2赞 309
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,330评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,205评论 3赞 312
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,567评论 3赞 298
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,889评论 0赞 17
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,160评论 1赞 250
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,475评论 2赞 341
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,650评论 2赞 335

推荐阅读更多精彩内容

  • Java初级面试题
    1. Java基础部分 基础部分的顺序：基本语法，类相关的语法，内部类的语法，继承相关的语法，异常的语法，线程的语...
    子非鱼_t_阅读 31,493评论 18赞 399
  • Java 性能调优指南之 Java 集合概览
    【编者按】本文作者为拥有十年金融软件开发经验的 Mikhail Vorontsov，文章主要概览了所有标准 Jav...
    OneAPM_Official阅读 879评论 0赞 7
  • Java后台面试 常见问题
    从三月份找实习到现在，面了一些公司，挂了不少，但最终还是拿到小米、百度、阿里、京东、新浪、CVTE、乐视家的研发岗...
    时芥蓝阅读 42,137评论 11赞 349
  • 月亮的脸
    看着你的脸， 就像看见月亮， 照亮我的夜晚 这是只属于我的月亮， 我想把她摘下来 偷偷的带回家里 白天我像太阳反射...
    关馨仁阅读 213评论 0赞 3
  • trouble
    还有什么情况能比现在的状况更加糟糕吗？！不得而知！世界上没有后悔药，悔不当初没有用！年轻时的骄傲自大任性，现在都化...
    林小头阅读 181评论 0赞 0