iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 21
0

今天我們要來談談 Sorting,也就是排序。排序看似不起眼,但其實在電腦的世界扮演了許多關鍵的角色,例如當我們要更有效率地搜尋出某個東西的時候,又例如我們要按照順序去處理資料的時候等等。快速且好的排序方法還可以提升用戶的體驗。所以今天我們就來看看在這四個語言之中一些關於 Sorting 的大小事吧!


Python

  • 首先我們先來看最簡單的一個內建函式 sorted,可以幫助我們對一個 List 進行 Sorting。sorted 會回傳一個新的 List,不會改變本來的 List。而新的 List 預設會是以 Ascending order 排序 (由小到大),但如果我們將 Flog reverse 改成 True 的話就會得到 Descending order (由大到小)。除了可以對 List 排序外,sorted 也可以對 Tuple 和 Set (本身沒有順序) 進行排序,但是 Output 都是 List,要自己小心 Casting 囉!sorted 背後用的演算法是 Timsort,簡單來說,Timsort 是结合了 Merge sort 和 Insertion sort 的演算法,有興趣可以參考這裡囉!
numbers = [5, 8, 3, 2]
new_numbers = sorted(numbers, reverse=False) # [2, 3, 5, 8]
  • 除了數字之外,我們也可以直接對一個字串使用 sorted,例如下面,我們針對 my_string 使用 sorted 會得到一個 List of characters,然後再透過 ''.join(<list of characters>) 把 List 組回新的字串囉!假設我們想要做 Sorting 的不是字元,而是 Word,例如一個句子中的 Words,那麼我們可以先透過字串的 split() Method 轉成 List of words 再進行排序。至於到底 String 類型的排序是根據什麼嗎?是根據首字進行字母排序,也就是根據該字元的 Unicode Code Point (可參考這裡),所以大小寫是有關係的唷!想知道某字元的 Unicode Code Point 可用 ord() 來得知。
my_string = "dacegbf"
my_sorted_string_list = sorted(my_string)
print(my_sorted_string_list)
my_sorted_string = ''.join(my_sorted_string_list)
print(my_sorted_string)
  • 假使一個 List 之中的元素有不同種 Type, 基本上是不能拿來排序的,因為不同類型的值彼此之間無法"比較"。在 sorted 還有一個很不錯的參數 keykey 的值是個函式,是一個我們可以自定義的函式來進行排序,例如下面我們給的 keylen 這個函式,這個函式會被拿來 iterate 每個字串並得到該字串的長度,於是就拿這個長度的值來進行排序,而得到 ['cat', 'apple', 'banana'] 囉!但這個自定義函式只能夠吃一個參數,並且要拿到對 List 中的每個元素都能操作唷!另外也可以直接使用 Lambda function (匿名函式) 就不用自己另外寫一個 Function 了 (像是 key=lambda x: x[::-1]),因為有了 key 所以讓我們可以對自定義的 Class 進行排序了!
words = ['banana', 'cat', 'apple']
new_words = sorted(words, key=len) # ['cat', 'apple', 'banana']
  • 另外我們注意到 List 本身也有一個方法叫做 sort() 這個跟 sorted 有點不同,第一個是只有 List 才有,第二個是 sort() 本身返回 None,排序是發生在原來的變數本身,也就是所謂的 In place。而 sort()sorted 都有 keyreverse 的參數。

Golang

  • 在 Golnag 已經有 Package sort 幫你實作了幾種 Sorting 的演算法,像是 Insertion sort、Heap sort、Quick sort 等等 (預設是 Quick sort),可以參考官方程式碼
  • 然而要讓我們自定義的 Struct 要能夠被排序其實也很簡單,只要實作了 sort.Interface 定義的三個方法 (前一天有談到如何實作介面) 就可以了 (下面的程式碼)。分別是用來獲取長度的 len()Less(i, j int) bool 表示當索引 i 的資料與 索引 j 的資料比較時,如果前者較小則返回 true,否則就會呼叫 Swap(i, j int) 來進行交換。至於在做排序時是呼叫該 Package 的 func Sort(data Interface)
type Interface interface {
        Len() int
        Less(i, j int) bool
        Swap(i, j int)
}
  • 讓我們看個例子。

上一篇
[Day 19] 終於來談談介面
下一篇
[Day 21] 什麼類型都可以
系列文
30 天把自己榨好榨滿的四週四語言大挑戰!30

尚未有邦友留言

立即登入留言