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

yipeiwu_com7年前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))

相关文章

Python脚本简单实现打开默认浏览器登录人人和打开QQ的方法

本文实例讲述了Python脚本简单实现打开默认浏览器登录人人和打开QQ的方法。分享给大家供大家参考,具体如下: 每天打开电脑第一件事应该就是打开人人刷一下,然后登上QQ。每次都这样很麻烦...

Python中的Function定义方法第1/2页

下面就先定义一个函数: 复制代码 代码如下:def foo(): print('function') foo() 在上述代码中,定义了一个名为foo的函数,这个函数没有参数。最后一行代码...

ubuntu 18.04搭建python环境(pycharm+anaconda)

ubuntu 18.04搭建python环境(pycharm+anaconda)

ubuntu 系统自带的 python 有多个版本,使用时难免会遇到环境变量出错,特别是当自动化运行脚本的时候。特别是近一个月来,实验室的小伙伴们的都倾心于 python。为了帮助小伙伴...

Pandas时间序列重采样(resample)方法中closed、label的作用详解

Pandas提供了便捷的方式对时间序列进行重采样,根据时间粒度的变大或者变小分为降采样和升采样: 降采样:时间粒度变大。例如,原来是按天统计的数据,现在变成按周统计。降采样会涉及到...

python 实现对文件夹中的图像连续重命名方法

python实现的对文件夹中的图像进行连续的重命名方法: import os class BatchRename(): def __init__(self): self.pa...