package main

import (
   "fmt"
   "strconv"
)

func RadixSort(seq []int) {
   // figures:位数,都是大于等于0的数
   var max = 0
   for _, s := range seq {
      if s > max {
         max = s
      }
   }
   var maxFigures = 1
    // 找到最大的那个值，看有几位数字  就要进行几轮排序 
   maxFigures = len(strconv.Itoa(max))
   figuresSort(seq,maxFigures)
}

func figuresSort(seq []int, mfg int) {
   num := 1
   for i := 0; i < mfg; i++ {
      var bucket [10][]int
      var result []int
      for _, s := range seq {
         n := s/num % 10 // 轮流吧个位 十位 百位 放入各自的桶里面
         bucket[n] = append(bucket[n], s)
      }

      // append
      for i := 0; i < 10; i++ {
         result = append(result, bucket[i]...)
      }


      for i := range seq {
         seq[i] = result[i]
      }
      // 十位 百位 千位
      num *= 10
   }
}

func main() {
   sequence := []int{6, 4, 7, 3, 9, 5, 1, 13, 0, 8, 22223, 10, 2}
   fmt.Printf("before: %d", sequence)

   RadixSort(sequence)
   fmt.Printf("after：%d", sequence)

}