Python实现的基数排序算法原理与用法实例分析

yipeiwu_com5年前Python基础

本文实例讲述了Python实现的基数排序算法。分享给大家供大家参考,具体如下:

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。

实现代码如下:

#-*- coding: UTF-8 -*-
import numpy as np
def RadixSort(a):
  i = 0                       #初始为个位排序
  n = 1                      #最小的位数置为1(包含0)
  max = np.max(a)            #得到带排序数组中最大数
  while max/(10**n) > 0:       #得到最大数是几位数
    n += 1
  while i < n:
    bucket = {}               #用字典构建桶
    for x in xrange(0,10):
      bucket.setdefault(x, [])  #将每个桶置空
    for x in a:                #对每一位进行排序
      radix =(x / (10**i)) % 10  #得到每位的基数
      bucket[radix].append(x) #将对应的数组元素加入到相应位基数的桶中
    j = 0
    for k in xrange(0, 10):
      if len(bucket[k]) != 0:    #若桶不为空
        for y in bucket[k]:     #将该桶中每个元素
          a[j] = y            #放回到数组中
          j += 1
    i += 1
if __name__ == '__main__':
  a = np.random.randint(0, 1000, size = 10)
  print "Before sorting..."
  print "---------------------------------------------------------------"
  print a
  print "---------------------------------------------------------------"
  RadixSort(a)
  print "After sorting..."
  print "---------------------------------------------------------------"
  print a
  print "---------------------------------------------------------------"

运行结果:

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程

希望本文所述对大家Python程序设计有所帮助。

相关文章

Python3.4实现远程控制电脑开关机

本文实例为大家分享了Python实现远程操控电脑的具体代码,供大家参考,具体内容如下 import poplib import sys import smtplib from...

Python实现判断给定列表是否有重复元素的方法

Python实现判断给定列表是否有重复元素的方法

本文实例讲述了Python实现判断给定列表是否有重复元素的方法。分享给大家供大家参考,具体如下: 题目很简单,只是简单温习一个方法,most_common,这是collection模块中...

Python读取txt某几列绘图的方法

晚上帮同学用Python脚本绘图,大概需求是读取一个txt文件的两列分别作为x和y的值,绘图即可,代码如下: #coding:utf-8 import numpy as np imp...

深入理解python try异常处理机制

深入理解python try异常处理机制 #python的try语句有两种风格 #一:种是处理异常(try/except/else) #二:种是无论是否发生异常都将执行最后的代码(t...

python中使用while循环的实例

python中使用while循环的实例

python中for循环用于针对集合中的每个元素的一个代码块,而while循环能实现满足条件下的不断运行。 使用while循环时,由于while只要满足条件就会执行代码,故必须指定结束条...