JS - sort以及演算法

之前在寫網頁時需要用到sort來根據資料的日期排序，本來一切都好好的，沒想到我在檔案打包好丟到gh pages瀏覽時，居然發現在ios上sort失效了！所以開始研究了這個功能是怎麼回事……

（題外話：問題最後解決了，但好像跟sort沒有關係……）

sort

會原地對一個陣列進行排序，預設是根據字串的unicode編碼位置
若是沒有帶compare function, 比較的兩個值會被轉換為字串
sort(compare function(a,b){}; 當a < b 時回傳-1, a>b時1, 相等時為0
演算法有分穩定/不穩定

＊穩定排序／不穩定排序
（小美，１０歲）（小明，８歲）（小王，１０歲）（強強，９歲）
此時若要按照年齡由小至大排序的話，會有兩種排法
1.（小明，８歲）（強強，９歲）（小美，１０歲）（小王，１０歲）
2.（小明，８歲）（強強，９歲）（小王，１０歲）（小美，１０歲）

參照原本的順序，原本小美是排在小王前面的，因此在第一個排序中，小美一樣在小王前面，就可稱為是穩定排序，在第二個排序中，小王被排在小美前面，就稱為不穩定排序。

用法
假設有一個陣列為[1, 3, 5, 65, 2, 4, 99]


[1, 3, 5, 65, 2, 4, 99].sort(function(a,b){ 
    if(a>b) return 1; //如果A比B大, 會被排在前面
    if(a<b) return -1; //如果A比B小, 會被排在後面
    return 0;
})
//或
[1, 3, 5, 65, 2, 4, 99].sort(function(a,b){ 
    return a>b?1:-1; //(三元運算子)
})

//或
[1, 3, 5, 65, 2, 4, 99].sort(function(a,b){ 
    return a-b; 
})

使用場合
在chrome的v8引擎中規定，當要排序的陣列長度<10時，使用插入排序（穩定），大於這個長度的陣列會用快速排序（不穩定）處理
演算法實作

4.1 氣泡排序
氣泡排序的規則：（來自維基）
1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素會是最大的數。
3. 針對所有的元素重複以上的步驟，除了最後一個。
4. 持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。

let  array = [{
                name: "aaa",
                age: 100
            },
            {
                name: "bbb",
                age: 20
            },
            {
                name: "ccc",
                age: 30
            },
            {
                name: "ddd",
                age: 20
            },
            {
                name: "eee",
                age: 30
            },
            {
                name: "fff",
                age: 40
            },
            {
                name: "ggg",
                age: 20
            },
            {
                name: "hhh",
                age: 20
            },
            {
                name: "iii",
                age: 30
            },
            {
                name: "jjj",
                age: 70
            },
            {
                name: "kkk",
                age: 90
            }
        ];

        function bubble(ary) {
            for (var i = 0; i < ary.length ; i++) {
                //跑迴圈 每次排完一定會有一個數字在正確位置(一定比後面的大), 所以下一輪要排的數字會固定少1
                for (var j = 0; j < ary.length - i - 1; j++) {
                        //將數字倆倆比較,前面的數字比後面大時,就移到後面
                    if (ary[j].age > ary[j + 1].age) {
                        var temp = ary[j];
                        ary[j] = ary[j + 1];
                        ary[j + 1] = temp;
                        console.log('後',ary[j], ary[j + 1]);
                    }
                }
            }
            return ary
        }

        bubble(data);

參考資料：[偷米騎巴哥] 20180412 前端踩雷日記(解開Sort不穩定現象之謎)

# JavaScript, 六角鼠年全馬挑戰賽, 演算法

JS - sort以及演算法

Your browser is out-of-date!