# sort ## 排序算法 排序也是在程序中經常用到的算法。無論使用冒泡排序還是快速排序，排序的核心是比較兩個元素的大小。如果是數字，我們可以直接比較，但如果是字符串或者兩個對象呢？直接比較數學上的大小是沒有意義的，因此，比較的過程必須通過函數抽象出來。通常規定，對于兩個元素`x`和`y`，如果認為`x < y`，則返回`-1`，如果認為`x == y`，則返回`0`，如果認為`x > y`，則返回`1`，這樣，排序算法就不用關心具體的比較過程，而是根據比較結果直接排序。 JavaScript的`Array`的`sort()`方法就是用于排序的，但是排序結果可能讓你大吃一驚： ~~~ // 看上去正常的結果: ['Google', 'Apple', 'Microsoft'].sort(); // ['Apple', 'Google', 'Microsoft']; // apple排在了最后: ['Google', 'apple', 'Microsoft'].sort(); // ['Google', 'Microsoft", 'apple'] // 無法理解的結果: [10, 20, 1, 2].sort(); // [1, 10, 2, 20] ~~~ 第二個排序把`apple`排在了最后，是因為字符串根據ASCII碼進行排序，而小寫字母`a`的ASCII碼在大寫字母之后。 第三個排序結果是什么鬼？簡單的數字排序都能錯？ 這是因為`Array`的`sort()`方法默認把所有元素先轉換為String再排序，結果`'10'`排在了`'2'`的前面，因為字符`'1'`比字符`'2'`的ASCII碼小。 > 如果不知道`sort()`方法的默認排序規則，直接對數字排序，絕對栽進坑里！ 幸運的是，`sort()`方法也是一個高階函數，它還可以接收一個比較函數來實現自定義的排序。 要按數字大小排序，我們可以這么寫： ~~~js var arr = [10, 20, 1, 2]; arr.sort(function (x, y) { if (x < y) { return -1; } if (x > y) { return 1; } return 0; }); // [1, 2, 10, 20] ~~~ 如果要倒序排序，我們可以把大的數放前面： ~~~ var arr = [10, 20, 1, 2]; arr.sort(function (x, y) { if (x < y) { return 1; } if (x > y) { return -1; } return 0; }); // [20, 10, 2, 1] ~~~ 默認情況下，對字符串排序，是按照ASCII的大小比較的，現在，我們提出排序應該忽略大小寫，按照字母序排序。要實現這個算法，不必對現有代碼大加改動，只要我們能定義出忽略大小寫的比較算法就可以： ~~~ var arr = ['Google', 'apple', 'Microsoft']; arr.sort(function (s1, s2) { x1 = s1.toUpperCase(); x2 = s2.toUpperCase(); if (x1 < x2) { return -1; } if (x1 > x2) { return 1; } return 0; }); // ['apple', 'Google', 'Microsoft'] ~~~ 忽略大小寫來比較兩個字符串，實際上就是先把字符串都變成大寫（或者都變成小寫），再比較。 從上述例子可以看出，高階函數的抽象能力是非常強大的，而且，核心代碼可以保持得非常簡潔。 最后友情提示，`sort()`方法會直接對`Array`進行修改，它返回的結果仍是當前`Array`： ~~~ var a1 = ['B', 'A', 'C']; var a2 = a1.sort(); a1; // ['A', 'B', 'C'] a2; // ['A', 'B', 'C'] a1 === a2; // true, a1和a2是同一對象 ~~~