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

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

代码如下:

# -*- coding: utf-8 -*-

def _counting_sort(A, i):
    """计数排序，以i位进行排序，以适用于基数排序。
    Args:
        A (Sequence): 排序数组
        i (int): 位数，从0开始而不是1
    """
    C = [0] * 10 # 任意位值范围为[0,9]
    A = [(a / (10 ** i) % 10, a) for a in A] # 元素i位值及其自身的元组的数组
    for k, a in A:
        C[k] = C[k] + 1
    for i in xrange(1, 10):
        C[i] = C[i] + C[i-1]
    B = [0] * len(A) # 结果数组
    for k, a in A[::-1]:
        B[C[k]-1] = a
        C[k] = C[k] - 1
    return B

def radix_sort(A, d):
    """基数排序，从最低位进行排序直到最高位：
    RADIX-SORT(A, d)
    1  for i ← 1 to d
    2    do use a stable sort to sort array A on digit i

Args:
        A (Sequence): 排序数组
        d (int): 最大数位数
    """
    for i in xrange(d): # 遍历位数，从低到高
        A = _counting_sort(A, i)
    return A

def rsort(A, d):
    """基数排序（桶排序版本）"""
    for i in xrange(d): # 遍历位数，从低到高
        S = [[] for _ in xrange(10)] # 存放[0,9]位数值所对应元素（[0-9]10个桶）
        for a in A: # 遍历元素
            S[a / (10 ** i) % 10].append(a) # 存放对应位数值的元素（元素当前位值在哪个桶就放进去）
        A = [a for b in S for a in b] # 以当前位数值排序好的A（依次从各桶里把元素拿出来）
    return A

if __name__ == '__main__':
    import random, timeit

items = range(10000)
    random.shuffle(items)

def test_sorted():
        print(items)
        sorted_items = sorted(items)
        print(sorted_items)

def test_radix_sort():
        print(items)
        sorted_items = radix_sort(items, 4) # [0,9999]，4位数
        print(sorted_items)

test_methods = [test_sorted, test_radix_sort]
    for test in test_methods:
        name = test.__name__ # test.func_name
        t = timeit.Timer(name + '()', 'from __main__ import ' + name)
        print(name + ' takes time : %f' % t.timeit(1))

赞 (0)

相关推荐

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

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

  • Python 冒泡，选择，插入排序使用实例

    最近学习了python基础,写一下3大排序练练手: 复制代码 代码如下: ''' Created on 2013-8-23 @author: codegeek ''' //冒泡排序 def bubble_sort(seq):     for i in range(len(seq)):         for j in range(i,len(seq)):             if seq[j] < seq[i]:                 tmp = seq[j]           

  • python实现bucket排序算法实例分析

    本文实例讲述了python实现bucket排序算法.分享给大家供大家参考.具体实现方法如下: def bucketSort(a, n, buckets, m): for j in range(m): buckets[j] = 0 for i in range(n): buckets[a[i]] += 1 i = 0 for j in range(m): for k in range(buckets[j]): a[i] = j i += 1 希望本文所述对大家的Python程序设计有所帮助.

  • 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中利用sorted()函数排序的简单教程

    排序算法 排序也是在程序中经常用到的算法.无论使用冒泡排序还是快速排序,排序的核心是比较两个元素的大小.如果是数字,我们可以直接比较,但如果是字符串或者两个dict呢?直接比较数学上的大小是没有意义的,因此,比较的过程必须通过函数抽象出来.通常规定,对于两个元素x和y,如果认为x < y,则返回-1,如果认为x == y,则返回0,如果认为x > y,则返回1,这样,排序算法就不用关心具体的比较过程,而是根据比较结果直接排序. Python内置的sorted()函数就可以对list进行排序:

  • python排序方法实例分析

    本文实例讲述了python排序方法.分享给大家供大家参考.具体如下: >>> def my_key1(x): ... return x % 10 ... >>> alist = [4, 5, 8, 1, 63, 8] >>> alist [4, 5, 8, 1, 63, 8] >>> alist.sort() # 默认升序排序 >>> alist [1, 4, 5, 8, 8, 63] >>> al

  • Python选择排序、冒泡排序、合并排序代码实例

    前两天刚装了python 3.1.1, 禁不住技痒写点code. 1.选择排序 复制代码 代码如下: >>> def SelSort(L):     length=len(L)     for i in range(length-1):         minIdx=i         minVal=L[i]         j=i+1         while j<length:             if minVal>L[j]:                 mi

  • python sort、sorted高级排序技巧

    Python list内置sort()方法用来排序,也可以用python内置的全局sorted()方法来对可迭代的序列排序生成新的序列. 1)排序基础 简单的升序排序是非常容易的.只需要调用sorted()方法.它返回一个新的list,新的list的元素基于小于运算符(__lt__)来排序. 复制代码 代码如下: >>> sorted([5, 2, 3, 1, 4]) [1, 2, 3, 4, 5] 你也可以使用list.sort()方法来排序,此时list本身将被修改.通常此方法不如s

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

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

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

    python算法学习之计数排序实例 复制代码 代码如下: # -*- coding: utf-8 -*- def _counting_sort(A, B, k):    """计数排序,伪码如下:    COUNTING-SORT(A, B, k)    1  for i ← 0 to k // 初始化存储区的值    2    do C[i] ← 0    3  for j ← 1 to length[A] // 为各值计数    4    do C[A[j]] ← C[A

  • Python基础学习之类与实例基本用法与注意事项详解

    本文实例讲述了Python基础学习之类与实例基本用法与注意事项.分享给大家供大家参考,具体如下: 前言 和其他编程语言相比,Python用非常少的新语法和语义将类加入到语言中.Python的类提供了面向对象编程的所有标准特性:类继承机制允许多个基类,派生类可以覆盖它基类的任何方法,一个方法可以调用基类中相同名称的的方法.对象可以包含任意数量和类型的数据.和模块一样,类也拥有Python天然的动态特性:它们在运行时创建,可以在创建后修改. Python的类 Python类实例时,先调用__new_

  • python算法学习双曲嵌入论文方法与代码解析说明

    python算法学习双曲嵌入论文方法与代码解析说明

    目录 1. 方法说明 损失函数 梯度下降 梯度求解 2. 代码训练过程 3. 结果表现 其他参考资料 本篇接上一篇:python算法学习双曲嵌入论文代码实现数据集介绍 1. 方法说明 首先学习相关的论文中的一些知识,并结合进行代码的编写.文中主要使用Poincaré embedding. 对应的python代码为: def dist1(vec1, vec2): # eqn1 diff_vec = vec1 - vec2 return 1 + 2 * norm(diff_vec) / ((1 -

  • python算法学习双曲嵌入论文代码实现数据集介绍

    python算法学习双曲嵌入论文代码实现数据集介绍

    目录 1. 目标 Python 代码依赖库 2. 数据集 数据展示 学习的文章: Poincaré Embeddings for Learning Hierarchical Representations 主要参考的代码: poincare_embeddings gensim – Topic Modelling in Python - poincare.py 由于有些代码难以运行,有些比较难读(封装程度非常高)甚至有些代码写得存在一些问题.因此我们重新按照论文的设置,利用Python重现了对应的

  • python算法学习之桶排序算法实例(分块排序)

    复制代码 代码如下: # -*- coding: utf-8 -*- def insertion_sort(A):    """插入排序,作为桶排序的子排序"""    n = len(A)    if n <= 1:        return A    B = [] # 结果列表    for a in A:        i = len(B)        while i > 0 and B[i-1] > a:      

  • Python用于学习重要算法的模块pygorithm实例浅析

    本文实例讲述了Python用于学习重要算法的模块pygorithm.分享给大家供大家参考,具体如下: 这是一个能够随时学习重要算法的Python模块,纯粹是为了教学使用. 特点 易于使用 容易理解的文档 快速获取算法的源代码 随时获取时间复杂度 安装 仅需在终端中执行以下命令: pip3 install pygorithm *如果你使用的是Python 2.7,请使用pip来安装.如果存在用户权限的限制,你可能需要使用pip install --user pygorithm这个命令来安装. 或者

  • Python常用算法学习基础教程

    Python常用算法学习基础教程

    本节内容 算法定义 时间复杂度 空间复杂度 常用算法实例 1.算法定义 算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制.也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出.如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题.不同的算法可能用不同的时间.空间或效率来完成同样的任务.一个算法的优劣可以用空间复杂度与时间复杂度来衡量. 一个算法应该具有以下七个重要的特征: ①有穷性(Fin

  • Python基础学习之函数方法实例详解

    本文实例讲述了Python基础学习之函数方法.分享给大家供大家参考,具体如下: 前言 与其他编程语言一样,函数(或者方法)是组织好的,可重复使用的,用来实现单一,或相关联功能的代码段. python的函数具有非常高的灵活性,可以在单个函数里面封装和定义另一个函数,使编程逻辑更具模块化. 一.Python的函数方法定义 函数方法定义的简单规则: 1. 函数代码块以 def 关键词开头,后接函数标识符名称和圆括号(). 2. 任何传入参数和自变量必须放在圆括号中间.圆括号之间可以用于定义参数. 3.

  • 10个python3常用排序算法详细说明与实例（快速排序，冒泡排序，桶排序，基数排序，堆排序，希尔排序，归并排序，计数排序）

    我简单的绘制了一下排序算法的分类,蓝色字体的排序算法是我们用python3实现的,也是比较常用的排序算法. Python3常用排序算法 1.Python3冒泡排序--交换类排序 冒泡排序(Bubble Sort)也是一种简单直观的排序算法. 它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来. 走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 作为最简单的排序算法

随机推荐