Python實現基數排序

  • 2020 年 1 月 10 日
  • 筆記

#! /usr/bin/env python  #coding=utf-8    #基於桶排序的基數排序  from random import randint    def RadixSort(list,d):      for k in xrange(d):#d輪排序          s=[[] for i in xrange(10)]#因為每一位數字都是0~9,故建立10個桶          '''對於數組中的元素,首先按照最低有效數字進行             排序,然後由低位向高位進行。'''          for i in list:              '''對於3個元素的數組[977, 87, 960],第一輪排序首先按照個位數字相同的                 放在一個桶s[7]=[977],s[7]=[977,87],s[0]=[960]                 執行後list=[960,977,87].第二輪按照十位數,s[6]=[960],s[7]=[977]                 s[8]=[87],執行後list=[960,977,87].第三輪按照百位,s[9]=[960]                 s[9]=[960,977],s[0]=87,執行後list=[87,960,977],結束。'''              s[i/(10**k)%10].append(i) #977/10=97(小數捨去),87/100=0          list=[j for i in s for j in i]      return list    if __name__ == '__main__':      a=[randint(1,999) for i in xrange(10)]#最多是三位數,因此d=3      print a      a=RadixSort(a,3)#將排好序的數組再賦給a!!!!      print a