Python实现的计数排序算法示例

yipeiwu_com5年前Python基础

本文实例讲述了Python实现的计数排序算法。分享给大家供大家参考,具体如下:

计数排序是一种非常快捷的稳定性强的排序方法,时间复杂度O(n+k),其中n为要排序的数的个数,k为要排序的数的组大值。计数排序对一定量的整数排序时候的速度非常快,一般快于其他排序算法。但计数排序局限性比较大,只限于对整数进行排序。计数排序是消耗空间发杂度来获取快捷的排序方法,其空间发展度为O(K)同理K为要排序的最大值。

计数排序的基本思想为一组数在排序之前先统计这组数中其他数小于这个数的个数,则可以确定这个数的位置。例如要排序的数为 7 4 2 1 5 3 1 5;则比7小的有7个数,所有7应该在排序好的数列的第八位,同理3在第四位,对于重复的数字,1在1位和2位(暂且认为第一个1比第二个1小),5和1一样位于6位和7位。

示例代码:

#! /usr/bin/env python
#coding=utf-8
#计数排序
def CountingSort(a, b, k):
  #c=[0]*(k+1) #let c[0...k] be an all 0 array
  #c=[0 for i in range(0,k+1)]
  c=[]
  for i in range(k+1):
    c.append(0)
  for j in range(len(a)):
    c[a[j]] = c[a[j]] + 1
  for i in range(1, k+1):
    c[i] = c[i] + c[i-1]
  for j in range(len(a)-1, -1, -1):
    b[c[a[j]]-1] = a[j]#!!!!!减一是关键
    c[a[j]] = c[a[j]] - 1
  print b
if __name__ == '__main__':
  a=[2, 5, 3, 0, 2, 3, 0, 3]
  #b=[0]*len(a)
  b=[None for i in range(len(a))]
  print "【听图阁-专注于Python设计】测试结果:"
  CountingSort(a, b, max(a))

运行结果:

PS:关于排序算法的详细说明还可参考本站在线工具:

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具
http://tools.jb51.net/aideddesign/paixu_ys

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程

希望本文所述对大家Python程序设计有所帮助。

相关文章

python的Crypto模块实现AES加密实例代码

python的Crypto模块实现AES加密实例代码

本文主要探索的是python的Crypto模块实现AES加密,分享了具体实现代码,下面看看具体内容。 学了使用Crypto模块的AES来加密文件,现在记录下来便于后边儿查看。 在刚开始...

Python函数中不定长参数的写法

Python函数中不定长参数的写法

1、不定长参数的写法,用 *变量名 表示 2、不定长参数累加 3、不定长参数,使用**c接受m=23,n=56的值; 传参时,a必写,b、c可以缺省 def fun(a, b,...

python定时关机小脚本

本文实例为大家分享了python定时关机的具体代码,供大家参考,具体内容如下 # coding: utf-8 import sys import os import time r...

python 使用while写猜年龄小游戏过程解析

需求: 用户一轮有三次机会进行猜年龄游戏,每猜一次会给相应的提示告知用户应该往大点猜或者小点猜,三次机会用完以后,可选择重新再来三次机会。 思路: 首先定义一个初始年龄为25和初始次数0...

python win32 简单操作方法

源由 刚开始是帮朋友做一个按键精灵操作旺信的脚本,写完后各种不稳定;后来看到python可以操作win32相关的api,恰好这一段时间正在学习python,感觉练手的时候到了~~~ 下载...