關於Sort排序這件不小的小事

前言

先前寫了一篇關於JS陣列20種操作的方法學員中對於Sort()有點疑問不清楚原理,在被詢問時我自己也突然疑惑了一下,所以決定自己針對Sort()來做一下研究了解原理。

Sort 說明

首先在 MDN 官網中說明 Sort 是會陣列進行排序的一個方法,但排序不一定是正確的,主要預設的排序是根據字串的 Unicode 編碼位置(code points)而定。

Unicode 是什麼?

所謂的 Unicode 就是類似以下這張圖

但是這邊就不做多餘的解釋,主要是了解 Unicode 是什麼而已。

Sort 基本用法

本講解會使用的範例陣列。

1
any = ['D', 'C', 'A', 'E', 'B'];

首先 sort 會在兩個值之間做比較,所以 sort 的寫法是這樣

1
2
3
4
any = ['D', 'C', 'A', 'E', 'B'];
any.sort(function(a,b){
....
})

先來看看 a 跟 b 帶入的值是什麼,我這邊會寫入一個 i 來做紀錄比較次數更方便了解它執行順序。

1
2
3
4
5
6
7
let i = 1
any = ['D', 'C', 'A', 'E', 'B'];
any.sort(function(a,b){
console.log(`a:${a}, 第${i}次比較`)
console.log(`b:${b}, 第${i}次比較`)
i++;
})

由此可知 a 所代表的是陣列第二個,b 則是陣列第一個,但是因為我排序已經排好了,看不出所以然,這邊另外再做一次打亂的排序並改用數字會更清楚。

1
2
3
4
5
6
7
let i = 1
any = [10, 5, 19, 66, 20];
any.sort(function(a,b){
console.log(`a:${a}, 第${i}次比較`)
console.log(`b:${b}, 第${i}次比較`)
i++;
})

結果也是一樣 a 代表陣列第二個, b 則代表第一個,可是會發現陣列還沒做排序,因為我還沒 return 值回來,所以必須 return 返回一組新陣列才可以。

這邊先前用所做的範例 return a > b ? 1 : -1 做陣列排序。

稍微講解一下 a > b ? 1 : -1 是什麼東西。
表示式 A ? True : false
?: 叫做三元運算子,是 if else 的縮寫,條件放在 A ,若為是就是 true,若答案為否就是 false。

所以 return a > b ? 1 : -1 就是答案是 true 的時候,陣列索引就會 +1,若陣列為 false 陣列索引就會 -1。

1
2
3
4
5
6
7
8
let i = 1
any = [10, 5, 19, 66, 20];
any.sort(function(a,b){
console.log(`a:${a}, 第${i}次比較`)
console.log(`b:${b}, 第${i}次比較`)
i++;
return a > b ? 1 : -1
})

這邊可以發現 Sort 執行 了 7 次比較呢!

比前面原本的 4 次還多了整整 3 次比較,原因為什麼?

我們來看看當 a > b 它會出現什麼(這邊會寫比較多 console.log 更詳細了解它的運作)

1
2
3
4
5
6
7
8
9
let i = 1
any = [10, 5, 19, 66, 20];
any.sort(function(a,b){
console.log(`a:${a}, 第${i}次比較`)
console.log(`b:${b}, 第${i}次比較`)
console.log(`第 ${i} 次比較 a(${a}) > b(${b}),結果${a > b} `);
i++;
return a > b ? 1 : -1
})

相信看到 console.log() 對於 sort 的比較應該會更清楚。

另外 sort 會以高效率的速度做數字之間的比較,但是因為比較次數有點不清楚,所以在增加一些資料上去

1
2
3
4
5
6
7
8
9
let i = 1
any = [10, 5, 19, 66, 20, 2 , 1];
any.sort(function(a,b){
console.log(`a:${a}, 第${i}次比較`)
console.log(`b:${b}, 第${i}次比較`)
console.log(`第 ${i} 次比較 a(${a}) > b(${b}),結果${a > b} `);
i++;
return a > b ? 1 : -1
})

拆解分析

那麼依照先前所撰寫的範例來拆解來看看,另外會加入一行 console.log() 來了解每一次陣列的變化。

1
2
3
4
5
6
7
8
9
let i = 1
any = [14, 30, 35, 42, 5, 16, 70, 98, 19, 100];
any.sort(function(a,b){
console.log(i);
console.log(`第 ${i} 次比較 a(${a}) > b(${b}),結果${a > b} `);
console.log(`第 ${i}${any}`);
i++;
return a > b ? 1 : -1
})

可以發現一件很奇妙的事情,只要出現 false 就會跟前面贏 (true) 做 PK,感覺就跟淘汰積分制一樣。

最終結果就會像這樣子。

1
[5, 14, 16, 19, 30, 35, 42, 70, 98, 100]

更詳細的說明可以參考 MDN

0%