1 .时段排序(Bucket Sort ) )
基本的想法是：
将排序的要素分类为不同的疼痛。 首先扫描序列，求出最大值maxV和最小值minV，设铲斗个数为k，将区间[minV，maxV]均匀分成k个区间，每个区间为一个铲斗。 将序列中的元素指定给各自的桶。
对每个桶中的元素进行排序。 可以选择任何排序算法。
把每个桶里的元素组成一个大而有序的排列。
假设数据均匀分布，则每桶元素的平均个数为n/k。 假设快速排序选择对每个桶中的元素进行排序，每个排序的时间复杂度为o(n/klog )n/k )。 总的时间复杂度为o(n ) o ) k ) o ) n/klog ) n/k )=o ) nnlog ) n/k )=o ) nnlogn-nlogk。 当k接近n时，排序桶的时间复杂度所喜悦的云被认为是o(n )。 也就是说，桶越多时间效率越高，桶越多空间越大。
2 .计数排序)。
是考虑打开最大值-最小1长度数组的o(n )的排序算法，然后
定额。 扫描原始数组一次，以当前值- minValue作为下标，将该下标的计数器加1。
收集。 扫描一次计数器数组，按顺序收集值。
例如，对于nums=[ 2，1，3，1，5 ]，首先扫描以获取最小值和最大值，然后打开长度为5的计数器数组counter，因为maxValue=5，minValue=1。
定额。 统计各要素的出现频率，得到counter=[ 2，1，1，0，1 ]，例如counter[0]表示值0 minValue=1出现了2次。 收集。 counter[0]=2表示1出现了两次，它在原数组中写入两个1，counter[1]=1表示2出现了一次，它在原数组中写入2，依次类推，最终原数组为[ 1，1 ] 计数排序本质上是一种特殊的桶排序，桶的个数最大时是计数排序。
# includeiostreamusingnamespacestd； int main () {int N，n； //N为数据个数while(cinn ) { int a[1001]={0}； 每当wile(n-- )//n递减时，数值为n cinn； //n表示各数据的值a[n]=1。 //1每个数据的出现次数为1 ) for(intI=0； i1001； I ) if(a[I] ) coutiendl； } return 0； } 3.基数排序
是非比较排序算法，时间复杂度为o(n )。 主要想法是，
将所有要排序的整数(请注意，它们必须是非负整数)统一为相同位数的整数，并在位数少之前填充零。 一般是十进制，可以是十六进制也可以是二进制。 因此，以找到最大值，得到最长的位数为前提，将k进制数中的最长作为位数d。 从最下位开始依次进行一次稳定排序。 这样从最低到最高排序完成后，整个序列就变成了有序的序列。
例如，有0、123、45、386、106的整数数组。 以下是排序过程。 第一个排序，1位，000 123 045 386 106，没有任何变化
第二次排序，10位，000 106 123 045 386
第三次排序，百位，000 045 106 123 386
结果，0、45、106、123、386，排序完成。
为什么同位数的排序子程序使用稳定的排序？ 因为稳定排序可以保留上次排序的成果。 例如，10位数的排序过程保留1位数的排序结果，而100位数的排序过程保留10位数的排序结果。 可以使用二进制吗？ 是的。 可以将排序序列中的每个整数视为由01组成的二进制值。 这样的话，任何一个非负的整数序列都可以使用基数排序算法吧。 理论上，假设排序对象序列的最大整数为2 4 . 1，则最大位数d=64，时间复杂度为o(64n )。 请注意，任何非负整数序列都可以在线性时间内排序。
既然任意非负整数序列都可以在线性时间内排序，那么基于比较排序的算法有什么意义呢？ 基于比较的排序算法时间复杂度为o(nlogn )，且看起来比o ) 64n )慢，但仔细想想，事实并非如此。 o ) nlogn )的序列非常长，只有达到两个元素时才等于o ) 64n )。 因此，64这个常数系数太大了，在大多数情况下，n远远小于2。
使用二进制数时，k=2最小，位数d最大，时间复杂度O(nd变大，空间复杂度o[nk]变小。 以基数为最大值时，k=maxV为最大，d=1为最小，此时时间复杂度O(nd变小，但空间复杂度o[nk]急剧增大，此时基数排序退化为计数器排序。
首先比较时间的复杂性和空间的复杂性。
在此，d表示位数，k在基数分类中表示k进制数，在桶分类中表示桶的个数，maxV和minV表示原
元素的最大值和最小值。
首先，基数排序和计数排序都可以看作一桶排序。
计数排序本质上是一种特殊的桶排序，如果桶的个数达到最大(maxV-minV 1)，则为计数排序。
基数排序也是桶排序。 桶排序按值域划分桶，基数排序按位数划分； 基数排序可以视为多个桶排序，每一位都进行桶排序。
如果使用最大值作为基数，基数排序将退化为计数排序。
使用二进制数时，k=2最小，位数d最大，时间复杂度O(nd变大，空间复杂度o[nk]变小。 以基数为最大值时，k=maxV为最大，d=1为最小，此时时间复杂度O(nd变小，但空间复杂度o[nk]急剧增大，此时基数排序退化为计数器排序。
————————————————
这是CSDN博客“Rnan-prince”的原创文章，符合CC 4.0 BY-SA版权协议。 请附上原文出处的链接和本声明。
原文链接： https://blog.csdn.net/QQ _ 19446965/article/details/81517552