基于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 1 0 2 1 1 0 0 1]

输出

[1 2 3 5 5 6 7 10]

代码：

def bucket_sort(lst):
 buckets = [0] * ((max(lst) - min(lst))+1)
 for i in range(len(lst)):
  buckets[lst[i]-min(lst)] += 1
 res=[]
 for i in range(len(buckets)):
  if buckets[i] != 0:
   res += [i+min(lst)]*buckets[i]
 return res

二、基数排序：

例如，对如下数据序列进行排序。

192,221,12,23

可以观察到它的每个数据至多只有3位，因此可以将每个数据拆分成3个关键字：百位（高位）、十位、个位（低位）。如果按照习惯思维，会先比较百位，百位大的数据大，百位相同的再比较十位，十位大的数据大；最后再比较个位。基数排序方法对任一子关键字排序时必须借助于另一种排序方法，而且这种排序方法必须是稳定的。对于多关键字拆分出来的子关键字，它们一定位于0-9这个可枚举的范围内，这个范围不大，因此用桶式排序效率非常好。

代码：

from random import randint
def radix_sort(lis,d):
 for i in xrange(d):#d轮排序
  s = [[] for k in xrange(10)]#因为每一位数字都是0~9，故建立10个桶
  for j in lis:
   s[j/(10**i)%10].append(i)
  li = [a for b in s for a in b]
 return li

对数组中的元素按照从低位到高位排序，对于[192,221,12,23]第一轮按照个位数字相同的放在一组，是s[1] =[221],s[2]=[192,12],s[3]=23,第二轮按照十位数字进行排序，s[1]=[12],s[2]=[221,23],s[9]=[192],第三轮按照百位数字进行排序，s[0]=[12,23],s[1]=[192],s[2]=[221]

总结：

桶排序与基数排序常作为桶式排序出现，基数排序进行了多轮的桶排序。桶式排序不再是一种基于比较的排序方法，它是一种比较巧妙的排序方式，但这种排序方式需要待排序的序列满足以下两个特征：待排序列所有的值处于一个可枚举的范围之类；待排序列所在的这个可枚举的范围不应该太大，否则排序开销太大。可以用于学生成绩的排序，因为在若干学生中成绩的范围仅在100以内。

桶式排序的空间开销较大，它需要两个数组，第1个buckets数组用于记录“落入”各桶中元素的个数，进而保存各元素在有序序列中的位置，第2个数组用于缓存待排数据。它只能排整形数组。而且当k较大，而数组长度n较小，即k>>n时，辅助数组C[k+1]的空间消耗较大。

以上这篇基于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实现的计数排序算法示例

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

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

  • 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数据结构与算法之常见的分配排序法.分享给大家供大家参考,具体如下: 箱排序(桶排序) 箱排序是根据关键字的取值范围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实现计数排序与桶排序实例代码

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

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

    Python实现的桶排序算法示例

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

  • 基于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

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

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

  • Java桶排序之基数排序详解

    Java桶排序之基数排序详解

    基数排序也是桶排序的一种,也是跟样本数据强相关的,且基数排序要求样本数据是非负的十进制数,如果有小数或者负数,那么代码将要大量重写!这就是不基于比较的排序的弊端.一般来说,我们认为基数排序时间复杂度为O(N).但事实上,如果数据量很大很大,它的时间复杂度是O(N*log10(Max))(底数是10). 基数排序算法流程不是很难,但是以下代码实现方式比较骚,所以先放上一张截图,方便查看. 我们知道基数排序的实现流程是需要准备10个队列的,但是经典的实现流程却是利用了一个count数组来模拟了出队列

  • Python实现各种排序算法的代码示例总结

    Python实现各种排序算法的代码示例总结

    在Python实践中,我们往往遇到排序问题,比如在对搜索结果打分的排序(没有排序就没有Google等搜索引擎的存在),当然,这样的例子数不胜数.<数据结构>也会花大量篇幅讲解排序.之前一段时间,由于需要,我复习了一下排序算法,并用Python实现了各种排序算法,放在这里作为参考. 最简单的排序有三种:插入排序,选择排序和冒泡排序.这三种排序比较简单,它们的平均时间复杂度均为O(n^2),在这里对原理就不加赘述了.贴出来源代码. 插入排序: def insertion_sort(sort_lis

  • Python八大常见排序算法定义、实现及时间消耗效率分析

    本文实例讲述了Python八大常见排序算法定义.实现及时间消耗效率分析.分享给大家供大家参考,具体如下: 昨晚上开始总结了一下常见的几种排序算法,由于之前我已经写了好几篇排序的算法的相关博文了现在总结一下的话可以说是很方便的,这里的目的是为了更加完整详尽的总结一下这些排序算法,为了复习基础的东西,从冒泡排序.直接插入排序.选择排序.归并排序.希尔排序.桶排序.堆排序.快速排序入手来分析和实现,在最后也给出来了简单的时间统计,重在原理.算法基础,其他的次之,这些东西的熟练掌握不算是对之后的工作或者

  • python数据结构的排序算法

    python数据结构的排序算法

    目录 十大经典的排序算法 一.交换排序 1.冒泡排序(前后比较-交换) 2.快速排序(选取一个基准值,小数在左大数在右) 二.插入排序 1.简单插入排序(逐个插入到前面的有序数中) 2.希尔排序(从大范围到小范围进行比较-交换) 三.选择排序 1.简单选择排序(选择最小的数据放在前面) 2.堆排序(利用最大堆和最小堆的特性) 四.归并排序 五.其他排序 1.计数排序(字典计数-还原) 2.桶排序(链表) 3.基数排序 十大经典的排序算法 数据结构中的十大经典算法:冒泡排序.快速排序.简单插入排序

  • Python实现希尔排序,归并排序和桶排序的示例代码

    Python实现希尔排序,归并排序和桶排序的示例代码

    目录 1. 前言 2. 希尔排序 2.1 前后切分 2.2 增量切分 3. 归并排序 3.1 分解子问题 3.2 求解子问题 3.3 合并排序 4. 基数排序 5. 总结 1. 前言 本文将介绍希尔排序.归并排序.基数排序(桶排序). 在所有的排序算法中,冒泡.插入.选择属于相类似的排序算法,这类算法的共同点:通过不停地比较,再使用交换逻辑重新确定数据的位置. 希尔.归并.快速排序算法也可归为同一类,它们的共同点都是建立在分治思想之上.把大问题分拆成小问题,解决所有小问题后,再合并每一个小问题的

随机推荐