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程序设计有所帮助。

相关文章

Python+OpenCV目标跟踪实现基本的运动检测

Python+OpenCV目标跟踪实现基本的运动检测

目标跟踪是对摄像头视频中的移动目标进行定位的过程,有着非常广泛的应用。实时目标跟踪是许多计算机视觉应用的重要任务,如监控、基于感知的用户界面、增强现实、基于对象的视频压缩以及辅助驾驶等。...

python-opencv获取二值图像轮廓及中心点坐标的代码

python-opencv获取二值图像轮廓及中心点坐标代码: groundtruth = cv2.imread(groundtruth_path)[:, :, 0] h1, w1 =...

Python正则表达式实现简易计算器功能示例

本文实例讲述了Python正则表达式实现简易计算器功能。分享给大家供大家参考,具体如下: 需求:使用正则表达式完成一个简易计算器。 功能:能够计算简单的表达式。 如:1*2*((1+...

python数据类型_元组、字典常用操作方法(介绍)

元组 Python的元组与列表类似,不同之处在于元组的元素不能修改。 元组使用小括号,列表使用方括号。 元组创建很简单,只需要在括号中添加元素,并使用逗号隔开即可。 tp=(1,2,...

Python中计算三角函数之cos()方法的使用简介

 cos()方法返回x弧度的余弦值。 语法 以下是cos()方法的语法: cos(x) 注意:此函数是无法直接访问的,所以我们需要导入math模块,然后需要用math的静态对象...