您好、欢迎来到现金彩票网!
当前位置:秒速牛牛投注 > 桶链算法 >

分布排序(distribution sorts)算法大串讲

发布时间:2019-08-25 13:27 来源:未知 编辑:admin

  本文介绍的排序算法是基于分配、收集的排序算法,分配排序的基本思想:排序过程无须比较关键字,而是通过分配和收集过程来实现排序.它们的时间复杂度可达到线性阶:O(n)。不受比较排序算法时间复杂度O(nlogn)的下限限制。

  鸽巢排序(Pigeonhole sort),也被称作基数分类, 是一种时间复杂度为O(n)且在不可避免遍历每一个元素并且排序的情况下效率最好的一种排序算法。但它只有在差值(或者可被映射在差值)很小的范围内的数值排序的情况下实用,同时也要求元素个数(n)和成为索引的值(N)大小相当。

  鸽巢排序(Pigeonhole sort)算法的思想就是使用一个辅助数组,这个辅助数组的下标对应要排序数组的元素值即使用辅助数组的下标进行排序,辅助数组元素的值记录该下标元素值的在要排序数组中的个数。

  1.对于给定的一组要排序的数组,需要初始化一个空的辅助数组(“鸽巢”),把初始数组中的每个值作为一个key(“鸽巢”)即辅助数组的索引即是待排序数组的值。

  其实作者觉得鸽巢排序(Pigeonhole sort)的原理跟哈希表的原理类似——根据关键字的key就可以得到关键字的存储位置。

  桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是比较排序,不受到 O(n log n) 下限的影响。

  箱排序也称桶排序(Bucket Sort),其基本思想是:设置若干个箱子,依次扫描待排序的记录R[0],R[1],…,R[n-1],把关键字等于k的记录全都装入到第k个箱子里(分配),然后按序号依次将各非空的箱子首尾连接起来(收集)。

  【例】要将一副混洗的52张扑克牌按点数A2…JQK排序,需设置13个箱子,排序时依次将每张牌按点数放入相应的箱子里,然后依次将这些箱子首尾相接,就得到了按点数递增序排列的一副牌。

  若R[0..n-1]中关键字的取值范围是0到m-1的整数,则必须设置m个箱子。因此箱排序要求关键字的类型是有限类型,否则可能要无限个箱子。

  一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的,故箱子的类型应设计成链表为宜。

  4、为保证排序是稳定的,分配过程中装箱及收集过程中的连接必须按先进先出原则进行。

  每个箱子设为一个链队列。当一记录装入某箱子时,应做人队操作将其插入该箱子尾部;而收集过程则是对箱子做出队操作,依次将出队的记录放到输出序列中。

  若输入的待排序记录是以链表形式给出时,出队操作可简化为是将整个箱子链表链接到输出链表的尾部。这只需要修改输出链表的尾结点中的指针域,令其指向箱子链表的头,然后修改输出链表的尾指针,令其指向箱子链表的尾即可。

  分配过程的时间是O(n);收集过程的时间为O(m) (采用链表来存储输入的待排序记录)或O(m+n)。因此,箱排序的时间为O(m+n)。若箱子个数m的数量级为O(n),则箱排序的时间是线性的,即O(n),但最坏情况仍有可能是 O(n ^ 2)。

  桶排序只适用于关键字取值范围较小的情况,否则所需箱子的数目 m 太多导致浪费存储空间和计算时间。

  桶排序能够扩展为对整数元组序列进行排序,此时按照字典序排序。在面试的海量数据处理题目中,桶排序也很有作用。如对每天数以亿计的数据进行排序,直接排序即使采用nlgn的算法,依然是一件很恐怖的事情,内存也无法容纳如此多的数据。这时桶排序就可以有效地降低数据的数量级,再对降低了数量级的数据进行排序,可以得到比较良好的效果。

  基数排序(Radix Sort)是对桶排序的改进和推广。唯一的区别是基数排序强调多关键字,而桶排序没有这个概念,换句话说基数排序对每一种关键字都进行桶排序,而桶排序同一个桶内排序可以任意或直接排好序。

  若这d个分量中每个分量都是一个独立的关键字,则文件是多关键字的(如扑克牌有两个关键字:点数和花色);否则文件是单关键字的,

  (0≤jd)只不过是关键字中其中的一位(如字符串、十进制整数等)。

  多关键字中的每个关键字的取值范围一般不同。如扑克牌的花色取值只有4种,而点数则有13种。单关键字中的每位一般取值范围相同。

  (1) 若关键字是十进制整数,则按个、十等位进行分解,基数rd=10,C0=0,C9=9,d为最长整数的位数;

  (2) 若关键字是小写的英文字符串,则rd=26,Co=a,C25=z,d为字符串的最大长度。

  基数排序的基本思想是:从低位到高位依次对Kj(j=d-1,d-2,…,0)进行箱排序。在d趟箱排序中,所需的箱子数就是基数rd,这就是基数排序名称的由来。

  基数排序的时间复杂度是 O(k·n),其中n是排序元素个数,k是数字位数。注意这不是说这个时间复杂度一定优于O(n·log(n)),因为k的大小一般会受到 n 的影响。基数排序所需的辅助存储空间为O(n+rd)。

  基数排序应用到字符串处理的倍增算法里面,这个倍增算法,要反复的进行排序。如果排序能快一点,这个程序就能快很多。

  计数排序(Counting sort)是一种稳定的排序算法,和基数排序一样都是桶排序的变体。计数排序使用一个额外的数组C,其中第i个元素是待排序数组A中值小于等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。

  设被排序的数组为A,排序后存储到B,C为临时数组。所谓计数,首先是通过一个数组C[i]计算大小等于i的元素个数,此过程只需要一次循环遍历就可以;在此基础上,计算小于或者等于i的元素个数,也是一重循环就完成。下一步是关键:逆序循环,从length[A]到1,将A[i]放到B中第C[A[i]]个位置上。原理是:C[A[i]]表示小于等于a[i]的元素个数,正好是A[i]排序后应该在的位置。而且从length[A]到1逆序循环,可以保证相同元素间的相对顺序不变,这也是计数排序稳定性的体现。在数组A有附件属性的时候,稳定性是非常重要的。

  A中的元素不能大于k,而且元素要作为数组的下标,所以元素应该为非负整数。而且如果A中有很大的元素,不能够分配足够大的空间。所以计数排序有很大局限性,其主要适用于元素个数多,但是普遍不太大而且总小于k的情况,这种情况下使用计数排序可以获得很高的效率。由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上 1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。例如:计数排序是用来排序0到100之间的数字的最好的算法,但是它不适合按字母顺序排序人名。但是,计数排序可以用在基数排序中的算法来排序数据范围很大的数组。

  当输入的元素是 n 个 0 到 k 之间的整数时,它的运行时间是 Θ(n + k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。

  4.反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1

  Proxmap Sort是桶排序和基数排序的改进。ProxMap的排序采用不同的方法来排序,这在概念上是类似哈希。该算法使用桶技术对哈希方法进行改变,桶的大小不相同。

  先了解一个概念,一个数字3用3个1来表示,一个数字9用9个1来表示,珠排序中的珠指的是每一个1,它把每一个1想像成一个珠子,这些珠子被串在一起,想像下算盘和糖葫芦:

  图2(a)中有两个数字,4和3,分别串在四条线的最后一个珠子下落,因为它下边是空的,自由下落后变成图2(b),图2(c)中随机给了四个数字,分别是3,2,4,2,这些珠子自由下落,就变成了 (d)中,落完就有序了,2,2,3,4,以上就是珠排序的精华。

  这篇博文列举了选择排序的6个算法,基本可以掌握其中概要,管中窥豹,不求甚解。如果你有任何建议或者批评和补充,请留言指出,不胜感激,更多参考请移步互联网。

http://duchtech.com/tongliansuanfa/499.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有