text: from data import DataSeq
  
  Radix = 10
  
  def GetDigit(x, d):
      # 得到第d位的数字
      assert(d>0), "Error"
      return (x//10**(d-1))%10
      
  
  def CountDigits(x):
      # 得到x的位数
      cnt = 0
      while x:
          cnt+=1
          x//=10
      return cnt
  
  def RadixSortLSD(ds):
      MaxCountDigits = 0
      # 得到最大的位数
      for i in range(ds.length):
          tmp = CountDigits(ds.data[i])
          MaxCountDigits = tmp if MaxCountDigits < tmp else MaxCountDigits
  
      # 基数排序， LSD
      Bucket = {i:[] for i in range(Radix)}
      for i in range(ds.length):
          digit = GetDigit(ds.data[i], 1)
          Bucket[digit].append(ds.data[i])
  
      for d in range(2, MaxCountDigits+1):
          NewBucket = {i:[] for i in range(Radix)}
          for i in range(Radix):
              for x in Bucket[i]:
                  digit = GetDigit(x, d)
                  NewBucket[digit].append(x)
          del Bucket
          Bucket = NewBucket
  
      # 对原数组赋值
      idx = 0
      for i in range(Radix):
          for x in Bucket[i]:
              ds.SetVal(idx, x)
              idx += 1
  
  RadixSort = RadixSortLSD
  
      
  if __name__ == "__main__":
      ds=DataSeq(64)
      ds.Visualize()
      ds.StartTimer()
      RadixSortLSD(ds)
      ds.StopTimer()
      ds.SetTimeInterval(0)
      ds.Visualize()