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

赞 (0)

相关推荐

  • python 实现归并排序算法

    理论不多说: 复制代码 代码如下: #!/usr/bin/python import sys def merge(array, q, p, r): left_array = array[q:p+1] right_array = array[p+1:r+1] left_array_num = len(left_array) right_array_num = len(right_array) i, j , k= [0, 0, q] while i < left_array_num and j <

  • 八大排序算法的Python实现

    Python实现八大排序算法,具体内容如下 1.插入排序 描述 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的.个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2).是稳定的排序方法.插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素).在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中. 代码实现 def inser

  • python 实现插入排序算法

    复制代码 代码如下: #!/usr/bin/python def insert_sort(array): for i in range(1, len(array)): key = array[i] j = i - 1 while j >= 0 and key < array[j]: array[j + 1] = array[j] j-=1 array[j + 1] = key if __name__ == "__main__": array = [2, 4, 32, 64,

  • python 算法 排序实现快速排序

    QUICKSORT(A, p, r)是快速排序的子程序,调用划分程序对数组进行划分,然后递归地调用QUICKSORT(A, p, r),以完成快速排序的过程.快速排序的最差时间复杂度为O(n2),平时时间复杂度为O(nlgn).最差时间复杂度的情况为数组基本有序的时候,平均时间复杂度为数组的数值分布较为平均的时候.在平时情况下快速排序跟堆排序的时间复杂度都为O(nlgn),但是快速排序的常数项较小,所以要优于堆排序. PARTITION(A, p, r) 复制代码 代码如下: x ← A[r]

  • python简单实现基数排序算法

    本文实例讲述了python简单实现基数排序算法.分享给大家供大家参考.具体实现方法如下: from random import randint def main(): A = [randint(1, 99999999) for _ in xrange(9999)] for k in xrange(8): S = [ [] for _ in xrange(10)] for j in A: S[j / (10 ** k) % 10].append(j) A = [a for b in S for a

  • python计数排序和基数排序算法实例

    一.计数排序 计数排序(Counting sort)是一种稳定的排序算法 算法的步骤如下:找出待排序的数组中最大和最小的元素统计数组中每个值为i的元素出现的次数,存入数组C的第i项对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1当输入的元素是 n 个 0 到 k 之间的整数时,计数排序的时间复杂度为O(N+K),空间复杂度为O(N+K).当K不是很大时,这是一个很有效的线性排序算法. 以下是测试代

  • python冒泡排序算法的实现代码

    1.算法描述:(1)共循环 n-1 次(2)每次循环中,如果 前面的数大于后面的数,就交换(3)设置一个标签,如果上次没有交换,就说明这个是已经好了的. 2.python冒泡排序代码 复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- def bubble(l):    flag = True    for i in range(len(l)-1, 0, -1):        if flag:             flag = False

  • python算法学习之基数排序实例

    基数排序法又称桶子法(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些"桶"中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的比较性排序法. 复制代码 代码如下: # -*- coding: utf-8 -*- def _counting_sort(A, i):    """计数排序,以i

  • python选择排序算法的实现代码

    1.算法:对于一组关键字{K1,K2,-,Kn}, 首先从K1,K2,-,Kn中选择最小值,假如它是 Kz,则将Kz与 K1对换:然后从K2,K3,- ,Kn中选择最小值 Kz,再将Kz与K2对换.如此进行选择和调换n-2趟,第(n-1)趟,从Kn-1.Kn中选择最小值 Kz将Kz与Kn-1对换,最后剩下的就是该序列中的最大值,一个由小到大的有序序列就这样形成. 2.python 选择排序代码: 复制代码 代码如下: def selection_sort(list2):    for i in

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

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

    本文实例讲述了Python实现的基数排序算法.分享给大家供大家参考,具体如下: 基数排序(radix sort)属于"分配式排序"(distribution sort),又称"桶子法"(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些"桶"中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率

  • Python实现的插入排序算法原理与用法实例分析

    Python实现的插入排序算法原理与用法实例分析

    本文实例讲述了Python实现的插入排序算法原理与用法.分享给大家供大家参考,具体如下: 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的.个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2).是稳定的排序方法 插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素).在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中. 插

  • Python实现的堆排序算法原理与用法实例分析

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

    本文实例讲述了Python实现的堆排序算法.分享给大家供大家参考,具体如下: 堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法.堆是一个近似完全二叉树的结构,并同时满足堆性质:即子结点的键值或索引总是小于(或者大于)它的父节点. 具体代码如下: #-*- coding: UTF-8 -*- import numpy as np def MakeHeap(a): for i in xrange(a.size / 2 - 1, -1, -1):#对非叶子节点的子节点进行调节,构建

  • Python设计模式之解释器模式原理与用法实例分析

    Python设计模式之解释器模式原理与用法实例分析

    本文实例讲述了Python设计模式之解释器模式原理与用法.分享给大家供大家参考,具体如下: 解释器模式(Interpreter Pattern):给定一个语言,定义它的文法的一种表示,并定义一个解释器,这个解释器使用该表示来解释语言中的句子. 下面是一个解释器模式的demo: #!/usr/bin/env python # -*- coding:utf-8 -*- __author__ = 'Andy' """ 大话设计模式 设计模式--解释器模式 解释器模式(Interpr

  • Python设计模式之组合模式原理与用法实例分析

    Python设计模式之组合模式原理与用法实例分析

    本文实例讲述了Python设计模式之组合模式原理与用法.分享给大家供大家参考,具体如下: 组合模式(Composite Pattern):将对象组合成成树形结构以表示"部分-整体"的层次结构,组合模式使得用户对单个对象和组合对象的使用具有一致性. 下面是一个组合模式的demo: #!/usr/bin/env python # -*- coding:utf-8 -*- __author__ = 'Andy' """ 大话设计模式 设计模式--组合模式 组合模

  • Python设计模式之桥接模式原理与用法实例分析

    Python设计模式之桥接模式原理与用法实例分析

    本文实例讲述了Python设计模式之桥接模式原理与用法.分享给大家供大家参考,具体如下: 桥接模式(Bridge Pattern):将抽象部分与它的实现部分分离,使它们都可以独立地变化. 下面是一个桥接模式的demo: #!/usr/bin/env python # -*- coding:utf-8 -*- __author__ = 'Andy' """ 大话设计模式 设计模式--桥接模式 桥接模式(Bridge Pattern):将抽象部分与它的实现部分分离,使它们都可以独

  • Python设计模式之迭代器模式原理与用法实例分析

    Python设计模式之迭代器模式原理与用法实例分析

    本文实例讲述了Python设计模式之迭代器模式原理与用法.分享给大家供大家参考,具体如下: 迭代器模式(Iterator Pattern):提供方法顺序访问一个聚合对象中各元素,而又不暴露该对象的内部表示. 下面是一个迭代器模式的demo: #!/usr/bin/env python # -*- coding:utf-8 -*- __author__ = 'Andy' """ 大话设计模式 设计模式--迭代器模式 迭代器模式(Iterator Pattern):提供方法顺序访

  • Python设计模式之命令模式原理与用法实例分析

    Python设计模式之命令模式原理与用法实例分析

    本文实例讲述了Python设计模式之命令模式原理与用法.分享给大家供大家参考,具体如下: 命令模式(Command Pattern):将请求封装成对象,从而使可用不同的请求对客户进行参数化:对请求排队或记录请求日志,以及支持可撤消的操作. 下面是一个命令模式的demo: #!/usr/bin/env python # -*- coding:utf-8 -*- __author__ = 'Andy' """ 大话设计模式 设计模式--命令模式 命令模式(Command Patt

  • Python多进程与服务器并发原理及用法实例分析

    Python多进程与服务器并发原理及用法实例分析

    本文实例分析了Python多进程与服务器并发原理及用法.分享给大家供大家参考,具体如下: 进程 什么是进程 进程:正在进行的一个过程或者说一个任务.而负责执行任务则是cpu. 进程与程序的区别 程序仅仅只是一堆代码而已,而进程指的是程序的运行过程. 并发与并行 无论是并行还是并发,在用户看来都是'同时'运行的,不管是进程还是线程,都只是一个任务而已,真是干活的是cpu,cpu来做这些任务,而一个cpu同一时刻只能执行一个任务 一 并发:是伪并行,即看起来是同时运行.单个cpu+多道技术就可以实现

  • Python实现的选择排序算法原理与用法实例分析

    Python实现的选择排序算法原理与用法实例分析

    本文实例讲述了Python实现的选择排序算法.分享给大家供大家参考,具体如下: 选择排序(Selection sort)是一种简单直观的排序算法.它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完. 比如在一个长度为N的无序数组中,在第一趟遍历N个数据,找出其中最小的数值与第一个元素交换,第二趟遍历剩下的N-1个数据,找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据,找出其中最小的数值与第N-1个元素

随机推荐