python实现计数排序与桶排序实例代码

计数排序

  1. 找到给定序列的最小值与最大值
  2. 创建一个长度为最大值-最小值+1的数组，初始化都为0
  3. 然后遍历原序列，并为数组中索引为当前值－最小值的值＋１
  4. 此时数组中已经记录好每个值的数量，自然也就是有序的了

例如：

计数排序实现

下面为列表的计数排序

def count_sort(s):
  """计数排序"""
  # 找到最大最小值
  min_num = min(s)
  max_num = max(s)
  # 计数列表
  count_list = [0]*(max_num-min_num+1)
  # 计数
  for i in s:
    count_list[i-min_num] += 1
  s.clear()
  # 填回
  for ind,i in enumerate(count_list):
    while i != 0:
      s.append(ind+min_num)
      i -= 1

if __name__ == '__main__':
  a = [3,6,8,4,2,6,7,3]
  count_sort(a)
  print(a)

计数排序的缺点

当数值中有非整数时，计数数组的索引无法分配

桶排序

桶排序原理：

  1. 桶排序与计数排序类似，但可以解决非整数的排序
  2. 桶排序相当于把计数数组划分为按顺序的几个部分
  3. 每一部分叫做一个桶，它来存放处于该范围内的数
  4. 然后再对每个桶内部进行排序，可以使用其他排序方法如快速排序
  5. 最后整个桶数组就是排列好的数据，再将其返回给原序列

举例：

桶排序实现

这里选择桶的数量为序列元素个数+1，范围分别是5等分与最大值，和上面那个图一样。

具体问题应该按照具体情况进行桶划分

这里桶内部排序直接调用了sorted

def bucket_sort(s):
  """桶排序"""
  min_num = min(s)
  max_num = max(s)
  # 桶的大小
  bucket_range = (max_num-min_num) / len(s)
  # 桶数组
  count_list = [ [] for i in range(len(s) + 1)]
  # 向桶数组填数
  for i in s:
    count_list[int((i-min_num)//bucket_range)].append(i)
  s.clear()
  # 回填，这里桶内部排序直接调用了sorted
  for i in count_list:
    for j in sorted(i):
      s.append(j)

if __name__ == '__main__':
  a = [3.2,6,8,4,2,6,7,3]
  bucket_sort(a)
  print(a) # [2, 3, 3.2, 4, 6, 6, 7, 8]

总结

计数排序与桶排序都是以牺牲空间换时间，虽然很快，但由于可能产生大量的空位置导致内存增大，尤其是计数排序。

桶排序中尽量使每个桶中的元素个数均匀分布最好

以上所述是小编给大家介绍的python计数排序与桶排序详解整合，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！

赞 (0)

相关推荐

  • 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计数排序和基数排序算法实例

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

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

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

    本文实例讲述了Python实现的计数排序算法.分享给大家供大家参考,具体如下: 计数排序是一种非常快捷的稳定性强的排序方法,时间复杂度O(n+k),其中n为要排序的数的个数,k为要排序的数的组大值.计数排序对一定量的整数排序时候的速度非常快,一般快于其他排序算法.但计数排序局限性比较大,只限于对整数进行排序.计数排序是消耗空间发杂度来获取快捷的排序方法,其空间发展度为O(K)同理K为要排序的最大值. 计数排序的基本思想为一组数在排序之前先统计这组数中其他数小于这个数的个数,则可以确定这个数的位置

  • 基于python进行桶排序与基数排序的总结

    本文首先举例阐述了两种排序方法的操作步骤,然后列出了用python进行的实现过程,最后对桶式排序方法的优劣进行了简单总结. 一.桶排序: 排序一个数组[5,3,6,1,2,7,5,10] 值都在1-10之间,建立10个桶: [0 0 0 0 0 0 0 0 0 0] 桶 [1 2 3 4 5 6 7 8 9 10] 桶代表的值 遍历数组,第一个数字5,第五个桶加1 [0 0 0 0 1 0 0 0 0 0] 第二个数字3,第三个桶加1 [0 0 1 0 1 0 0 0 0 0] 遍历后 [1 1

  • Python数据结构与算法之常见的分配排序法示例【桶排序与基数排序】

    本文实例讲述了Python数据结构与算法之常见的分配排序法.分享给大家供大家参考,具体如下: 箱排序(桶排序) 箱排序是根据关键字的取值范围1~m,预先建立m个箱子,箱排序要求关键字类型为有限类型,可能会有无限个箱子,实用价值不大,一般用于基数排序的中间过程. 桶排序是箱排序的实用化变种,其对数据集的范围,如[0,1) 进行划分为n个大小相同的子区间,每一个子区间为一个桶,然后将n非记录分配到各桶中.因为关键字序列是均匀分布在[0,1)上的,所以一般不会有很多记录落入同一个桶中. 以下的桶排序方

  • Python实现桶排序与快速排序算法结合应用示例

    Python实现桶排序与快速排序算法结合应用示例

    本文实例讲述了Python实现桶排序与快速排序算法结合应用的方法.分享给大家供大家参考,具体如下: #-*- coding: UTF-8 -*- import numpy as np from QuickSort import QuickSort def BucketSort(a, n): barrel = {} for i in xrange(0,n): barrel.setdefault(i, []) min = np.min(a) max = np.max(a) for x in a: f

  • Python实现的桶排序算法示例

    Python实现的桶排序算法示例

    本文实例讲述了Python实现的桶排序算法.分享给大家供大家参考,具体如下: 桶排序也叫计数排序,简单来说,就是将数据集里面所有元素按顺序列举出来,然后统计元素出现的次数.最后按顺序输出数据集里面的元素. 但是桶排序非常浪费空间, 比如需要排序的范围在0~2000之间, 需要排序的数是[3,9,4,2000], 同样需要2001个空间 注意: 桶排序不能排序小数 以下为从小到大代码实现 #!/usr/bin/env python # coding:utf-8 def bucketSort(num

  • python实现计数排序与桶排序实例代码

    python实现计数排序与桶排序实例代码

    计数排序 找到给定序列的最小值与最大值 创建一个长度为最大值-最小值+1的数组,初始化都为0 然后遍历原序列,并为数组中索引为当前值-最小值的值+1 此时数组中已经记录好每个值的数量,自然也就是有序的了 例如: 计数排序实现 下面为列表的计数排序 def count_sort(s): """计数排序""" # 找到最大最小值 min_num = min(s) max_num = max(s) # 计数列表 count_list = [0]*(ma

  • java 实现计数排序和桶排序实例代码

    java 实现计数排序和桶排序实例代码 目录 比较和非比较的区别 常见的快速排序.归并排序.堆排序.冒泡排序等属于比较排序.在排序的最终结果里,元素之间的次序依赖于它们之间的比较.每个数都必须和其他数进行比较,才能确定自己的位置. 在 冒泡排序 之类的排序中,问题规模为n,又因为需要比较n次,所以平均时间复杂度为O(n²).在 归并排序.快速排序 之类的排序中,问题规模通过分治法消减为logN次,所以时间复杂度平均 O(nlogn) . 比较排序的优势是,适用于各种规模的数据,也不在乎数据的分布

  • Angularjs添加排序查询功能的实例代码

    废话不多说了,直接给大家贴代码了,具体代码如下所示: <!DOCTYPE html> <html> <head lang="en"> <meta charset="UTF-8"> <title></title> <script type="text/javascript" src="angular-1.3.0.js"></script&g

  • python 把数据 json格式输出的实例代码

    有个要求需要在python的标准输出时候显示json格式数据,如果缩进显示查看数据效果会很好,这里使用json的包会有很多操作 import json date = {u'versions': [{u'status': u'CURRENT', u'id': u'v2.3', u'links': [{u'href': u'http://controller:9292/v2/', u'rel': u'self'}]}, {u'status': u'SUPPORTED', u'id': u'v2.2'

  • Python找出最小的K个数实例代码

    题目描述 输入n个整数,找出其中最小的K个数.例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,. 这个题目完成的思路有很多,很多排序算法都可以完成既定操作,关键是复杂度性的考虑.以下几种思路当是笔者抛砖引玉,如果读者有兴趣可以自己再使用其他方法一一尝试. 思路1:利用冒泡法 临近的数字两两进行比较,按照从小到大的顺序进行交换,如果前面的值比后面的大,则交换顺序.这样一趟过去后,最小的数字被交换到了第一位:然后是次小的交换到了第二位,...,依次直到第k个数,停

  • python 批量解压压缩文件的实例代码

    下面给大家介绍python 批量解压压缩文件的实例代码,代码如下所述: #/usr/bin/python#coding=utf-8import os,sys import zipfile open_path='e:\\data'save_path='e:\\data' os.chdir(open_path) #转到路径 #首先,通过zipfile模块打开指定位置zip文件 #传入文件名列表,及列表文件所在路径,及存储路径def Decompression(files,file_path,save

  • python按修改时间顺序排列文件的实例代码

    python按修改时间顺序排列文件,具体代码如下所示: import os def sort_file_by_time(file_path): files = os.listdir(file_path) if not files: return else: files = sorted(files, key=lambda x: os.path.getmtime(os.path.join(file_path, x)))#格式解释:对files进行排序.x是files的元素,:后面的是排序的依据.

  • Python实现七个基本算法的实例代码

    1.顺序查找 当数据存储在诸如列表的集合中时,我们说这些数据具有线性或顺序关系. 每个数据元素都存储在相对于其他数据元素的位置. 由于这些索引值是有序的,我们可以按顺序访问它们. 这个过程产实现的搜索即为顺序查找. 顺序查找原理剖析:从列表中的第一个元素开始,我们按照基本的顺序排序,简单地从一个元素移动到另一个元素,直到找到我们正在寻找的元素或遍历完整个列表.如果我们遍历完整个列表,则说明正在搜索的元素不存在. 代码实现:该函数需要一个列表和我们正在寻找的元素作为参数,并返回一个是否存在的布尔值

  • python 实现自动远程登陆scp文件实例代码

     python 实现自动远程登陆scp文件实例代码 实现实例代码: #!/usr/bin/expect if {$argc!=3} { send_user "Usage: $argv0 {path1} {path2} {Password}\n\n" exit } set path1 [lindex $argv 0] set path2 [lindex $argv 1] set Password [lindex $argv 2] spawn scp ${path1} ${path2} e

  • python将ansible配置转为json格式实例代码

    python将ansible配置转为json格式实例代码

    python将ansible配置转为json格式实例代码 ansible的配置文件举例如下,这种配置文件不利于在前端的展现,因此,我们用一段简单的代码将ansible的配置文件转为json格式的: [webserver] 192.168.204.70 192.168.204.71 [dbserver] 192.168.204.72 192.168.204.73 192.168.204.75 [proxy] 192.168.204.76 192.168.204.77 192.168.204.78

随机推荐