冒泡排序實現與性能優(yōu)化及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;
        //外層循環(huán)次數：總長度（arr.length） - 1
        for(int i=0;i<arr.length-1;i++){
            //外層每循環(huán)一次，內層循環(huán)依次減 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.冒泡排序的性能分析和算法優(yōu)化（外層循環(huán)優(yōu)化）

對于這樣的數組[2,1,3,4,5,6,7]瘩将，冒泡排序經過第一輪吟税，已經變成有序的了，但是的冒泡還是要繼續(xù)進行沒有營養(yǎng)的兩兩比較姿现，從而犧牲了時間肠仪。

由于冒泡排序的時間復雜度為O(n*n)。所以备典，當數據越多的時候越慢异旧，非常不適合大數據的排序，所以我們測試的時候也是用的長度為800的隨機數組提佣。

解決方法：如果用一個flag來判斷一下吮蛹，當前數組是否已經有序，如果有序就退出循環(huán)拌屏，這樣可以明顯的提高冒泡排序的性能潮针。

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;//若果沒有發(fā)生交換倚喂，則退出循環(huán)
            }
        }

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

4.冒泡排序第二種優(yōu)化（內層循環(huán)優(yōu)化）

記住最后一次交換發(fā)生位置的冒泡排序

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變量用來標記循環(huán)里最后一次交換的位置
        int k = arr.length - 1,pos = 0;
        //一共要排序size-1次
        for (i = 0; i < arr.length - 1; i++){
            //每次遍歷標志位都要先置為0每篷，才能判斷后面的元素是否發(fā)生了交換
            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;
                    //只要有發(fā)生了交換，flag就置為1
                    flag = 1;
                    //循環(huán)里最后一次交換的位置 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;
        }
    }
}

讀書感悟

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

所謂整理，就是整理每一件物品的"過去"矗晃。
一旦把東西放進袋子里仑嗅，就不會再使用了。
說的夸張一點喧兄，生而為人，對"什么能讓自己心動"的判斷是了解自己到底是一個怎樣的人的重要線索啊楚。
如果是男女共用衣柜的情況吠冤，我的建議是男士的衣服放在上層，女士的衣服放在下層恭理。擺放鞋子的時候拯辙，不管是男鞋還是女鞋都含有"支撐的基礎"的意思，性質相同颜价。所以涯保，只需簡單地把體積大、分量重的男鞋放在下層周伦，女鞋放在上層就能保持平衡夕春。
并不是"這個也扔，那個也扔"专挪，而是"有選擇地留下發(fā)光的東西及志，這才是理想生活的開端"。
無論丟棄物品還是擁有物品寨腔，都是為了讓自己幸福速侈。
教孩子折衣服，有助于培養(yǎng)他的整理習慣迫卢。
對有心動感的物品判斷速度會很快倚搬，拿著物品的手指很柔軟，看著物品的眼睛會閃閃發(fā)光乾蛤。如果拿著沒有心動感的物品每界，則雙手會瞬間停止動作，還會搖頭皺眉地作思考狀家卖，最后還會漫不經心地把物品扔到"留存處"盆犁。
為了珍惜真正富有價值的物品，必須首先丟棄已經完成了使命的物品篡九。
真正的必需品肯定是能讓自己幸福的東西谐岁，所以，應該積極地把必需品當作"心動物品"來對待。
凡是不符合"現在正使用""暫且需要""需要永存"這三項標準的文件伊佃，都應該毫不猶豫地全部丟掉窜司。
珍惜物品，從某種程度上來說也是珍惜自己的一種表現航揉。

經典故事

【一個佛陀在旅途中塞祈，碰到一個不喜歡他的人。連續(xù)好幾天帅涂，好長一段路议薪，那人用盡各種方法污蔑他。最后媳友，佛陀轉身問那人："若有人送你一份禮物斯议，但你拒絕接受，那么這份禮物屬于誰呢醇锚？"那人回答："屬于原本送禮的那個人哼御。"佛陀笑著說："沒錯。若我不接受你的謾罵焊唬，那你就是在罵自己恋昼？"那人摸摸鼻子走了。
啟發(fā)：只要心靈健康赶促，別人怎么想都影響不了我們液肌。若我們一味地在乎別人的想法或說法，就會失去自主權鸥滨【仄ǎ】

大神文章

【1】java實現冒泡排序
【2】冒泡排序優(yōu)化版,性能近乎翻倍
【3】黑馬程序員——冒泡排序的優(yōu)化和選擇排序
【4】冒泡排序算法及其兩種優(yōu)化
【5】Java中排序總結
【6】JDK7中的排序算法詳解--Collections.sort和Arrays.sort
【7】JDK1.7 Collections.sort Arrays.sort發(fā)現的問題
【8】java List 排序 Collections.sort()