# 3.3.4 - Radix Sort

### 1. 演算法

準備r-1個buckets(r進制)，假設資料中最大值的為數個數為d，則需要執行d回合。每回合執行下面兩個步驟

1. Distribution: 依照資料的位數值分派到對應的buckets
2. Merge: 依照buckets的編號合併資料

從個位數開始到d，共執行d回合。

e.g. $${179, 208, 306, 93, 859, 984, 55, 9, 271, 33} \_{10}$$ 

1. Distribution: 個位數

![](https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIV3mKAOAQkWo9dAhYo%2F-LIV43qns5HE4Nbu0j0Z%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-07-28%2016.49.33.jpg?alt=media\&token=48032fa8-607c-4c48-965e-466ca2a01f19)

1. Merge: {271, 93, 33, 984, 55, 306, 208, 179, 859, 9}

  2\. Distribution: 十位數

![](https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIV3mKAOAQkWo9dAhYo%2F-LIV4VeuiJd_X7jP5rBF%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-07-28%2016.51.23.jpg?alt=media\&token=db62997e-9632-4043-87af-ce51de76e11e)

  2\. Merge: {306, 208, 9, 33, 55, 859, 271, 179, 984, 93}

  3\. Distribution: 百位數

![](https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIV3mKAOAQkWo9dAhYo%2F-LIV5-4zdTCnM4GkFnD7%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-07-28%2016.53.17.jpg?alt=media\&token=04821088-cc75-4be1-a5f8-b28bedc2a1d6)

  3\. Merge: {9, 33, 55, 93, 179, 208, 271, 306, 859, 984}

### 2. 性質

* Time Complexity: $$O(n)$$ 

  n筆資料為r進制，其最大值有d位數，總共花 $$O(d\*(n+r))$$，d、r可視為常數。
* Space Complexity: $$O(r\*n)$$ 

  共需r個buckers，每個buckets的大小為n。

Radix sorting is a **unstable** sorting method.