Bucket sort & Radix sort

• 過去
  若是“comparison based”的sorting algorithm，一定需要O(nlogn)

• 突破點
  若key有特定的形式：整數且壓在很小的範圍，可以把整數當成index，指到另一個矩陣內

• Bucket sort
  複雜度：O(n) + O(N) ~= O(n)

  -->但加空間很麻煩

• Counting sort
  加上了
  1.Count array --> 算每個元素出現幾次
  2.Position array --> 元素一開始要放進去的位置
  3.Output array --> 直接參照position array來放

• 特性：
  Stable

• Lexicographic order
  從最小的開始排

• Radix sort
  為Lexicographic order的一種
  若有千位數、百位數、十位數、個位數，則可以從個位數排上去
  可以先轉為bit，再慢慢排序
  複雜度：O(d*(n+10))