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[j]] + 1
    5  ▷ C[i]包含等于i的元素个数
    6  for i ← 1 to k // 求计数和，确定<=各值的元素数
    7    do C[i] ← C[i] + C[i-1]
    8  ▷ C[i]包含小于或等于i的元素个数
    9  for j ← length[A] downto 1
    10   do B[C[A[j]]] ← A[j] // 将A[j]值放到对应位置
    11      C[A[j]] ← C[A[j]] - 1 // 避免元素相同时覆盖同一位置

T(n) = θ(n)

Args:
        A (Sequence): 原数组
        B (Sequence): 结果数组
        k (int): 值上限，假定了所有元素介于[0,k]
    """
    len_c = k + 1
    C = [0] * len_c
    for a in A:
        C[a] = C[a] + 1
    for i in range(1, len_c):
        C[i] = C[i] + C[i-1]
    for a in A[::-1]:
        B[C[a]-1] = a
        C[a] = C[a] - 1

def counting_sort(A):
    """假定A数组所有元素都介于[0,len(A)-1]"""
    B = [0] * len(A)
    _counting_sort(A, B, len(A) - 1)
    return B

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_counting_sort():
        print(items)
        sorted_items = counting_sort(items)
        print(sorted_items)

test_methods = [test_sorted, test_counting_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列表计数及插入的用法.分享给大家供大家参考.具体如下: 复制代码 代码如下: word=['a','b','c','d','e','f','g']//首个元素为元素0,word[0]=a   a=[num1:num2]                                     //从num1到num2的元素(不包括元素num2)     //若为负数,则代表倒数第几个 在对list进行操作时,append 追加,word.append(elements)

  • python中的字典详细介绍

    一.什么是字典? 字典是Python语言中唯一的映射类型. 映射类型对象里哈希值(键,key)和指向的对象(值,value)是一对多的的关系,通常被认为是可变的哈希表. 字典对象是可变的,它是一个容器类型,能存储任意个数的Python对象,其中也可包括其他容器类型. 字典类型与序列类型的区别: 1.存取和访问数据的方式不同. 2.序列类型只用数字类型的键(从序列的开始按数值顺序索引): 3.映射类型可以用其他对象类型作键(如:数字.字符串.元祖,一般用字符串作键),和序列类型的键不同,映射类型的

  • Python的Django框架中消息通知的计数器实现教程

    故事的开始:.count() 假设你有一个Notification Model类,保存的主要是所有的站内通知: class Notification(models.Model): """一个简化过的Notification类,拥有三个字段: - `user_id`: 消息所有人的用户ID - `has_readed`: 表示消息是否已读 """ user_id = models.IntegerField(db_index=True) has_re

  • Python入门教程 超详细1小时学会Python

    Python入门教程 超详细1小时学会Python

    为什么使用Python    假设我们有这么一项任务:简单测试局域网中的电脑是否连通.这些电脑的ip范围从192.168.0.101到192.168.0.200. 思路:用shell编程.(Linux通常是bash而Windows是批处理脚本).例如,在Windows上用ping ip 的命令依次测试各个机器并得到控制台输出.由于ping通的时候控制台文本通常是"Reply from ... " 而不通的时候文本是"time out ... " ,所以,在结果中进行

  • python strip()函数 介绍

    函数原型 声明:s为字符串,rm为要删除的字符序列 s.strip(rm)        删除s字符串中开头.结尾处,位于 rm删除序列的字符 s.lstrip(rm)       删除s字符串中开头处,位于 rm删除序列的字符 s.rstrip(rm)      删除s字符串中结尾处,位于 rm删除序列的字符 注意: 1. 当rm为空时,默认删除空白符(包括'\n', '\r',  '\t',  ' ') 例如: 复制代码 代码如下: >>> a = '     123'>>

  • Python闭包实现计数器的方法

    本文实例讲述了Python闭包实现计数器的方法.分享给大家供大家参考.具体实现方法如下: 先来看看专业的解释:闭包(Closure)是词法闭包(Lexical Closure)的简称,是引用了自由变量的函数.这个被引用的自由变量将和这个函数一同存在,即使已经离开了创造它的环境也不例外.所以,有另一种说法认为闭包是由函数和与其相关的引用环境组合而成的实体. 代码如下: #!/usr/bin/env python #coding=utf-8 def generate_counter(): CNT =

  • 用Python解决计数原理问题的方法

    用Python解决计数原理问题的方法

    前几天遇到这样一道数学题: 用四种不同颜色给三棱柱六个顶点涂色,要求每个点涂一种颜色,且每条棱的两个端点涂不同颜色,则不同的涂色方法有多少种? 当我看完题目后,顿时不知所措.于是我拿起草稿纸在一旁漫无目的地演算了一下,企图能找到解决方法.结果一无所获.于是打算通过程序算法解决这个问题.经过2个多小时的研究,终于完成了代码,并求得了答案. 由于Python写起来比较方便而且本人比较喜欢Python的语法,所以研究算法时我通常采用Python,此次也不例外.以下就是整个算法的实现过程. 两种算法 我

  • python计算书页码的统计数字问题实例

    本文实例讲述了python计算书页码的统计数字问题,是Python程序设计中一个比较典型的应用实例.分享给大家供大家参考.具体如下: 问题描述:对给定页码n,计算出全部页码中分别用到多少次数字0,1,2,3,4...,9 实例代码如下: def count_num1(page_num): num_zero = 0 num_one = 0 num_two = 0 num_three = 0 num_four = 0 num_five = 0 num_six = 0 num_seven = 0 nu

  • 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算法学习之桶排序算法实例(分块排序)

    复制代码 代码如下: # -*- 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算法与数据结构之冒泡排序实例详解

    一.冒泡排序介绍 冒泡排序(英语:Bubble Sort)是一种简单的排序算法.它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 二.冒泡排序原理 比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对.这一步做完,最后的元素应该会是最大的数. 针对所有的

  • C++ 计数排序实例详解

    C++ 计数排序实例详解

    计数排序 计数排序是一种非比较的排序算法 优势: 计数排序在对于一定范围内的整数排序时,时间复杂度为O(N+K)  (K为整数在范围)快于任何比较排序算法,因为基于比较的排序时间复杂度在理论上的上下限是O(N*log(N)). 缺点: 计数排序是一种牺牲空间换取时间的做法,并且当K足够大时O(K)>O(N*log(N)),效率反而不如比较的排序算法.并且只能用于对无符号整形排序. 时间复杂度: O(N)  K足够大时为O(K) 空间复杂度: O(最大数-最小数) 性能: 计数排序是一种稳定排序

  • java排序算法之_选择排序(实例讲解)

    选择排序是一种非常简单的排序算法,从字面意思我们就可以知道,选择就是从未排序好的序列中选择出最小(最大)的元素,然后与第 i 趟排序的第 i-1(数组中下标从 0 开始) 个位置的元素进行交换,第 i 个元素之前的序列就是已经排序好的序列.整个排序过程只需要遍历 n-1 趟便可排好,最后一个元素自动为最大(最小)值. 举个小例子: arr[] = {3,1,2,6,5,4} 第 1 趟排序: index = 0, min = 1, 交换后 -->  1,3,2,6,5,4 第 2 趟排序: in

  • 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算法学习之基数排序实例

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

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

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

  • Python算法的时间复杂度和空间复杂度(实例解析)

    算法复杂度分为时间复杂度和空间复杂度. 其作用: 时间复杂度是指执行算法所需要的计算工作量: 而空间复杂度是指执行这个算法所需要的内存空间. (算法的复杂性体现在运行该算法时的计算机所需资源的多少上,计算机资源最重要的是时间和空间(即寄存器)资源,因此复杂度分为时间和空间复杂度). 简单来说,时间复杂度指的是语句执行次数,空间复杂度指的是算法所占的存储空间 计算时间复杂度的方法: 用常数1代替运行时间中的所有加法常数 修改后的运行次数函数中,只保留最高阶项 去除最高阶项的系数 时间复杂度 算法的

随机推荐