排序算法之计数排序桶排序基数排序
1.计数排序：Counting Sort
计数排序是⼀个⾮基于⽐较的排序算法，该算法于1954年由 Harold H. Seward 提出，它的优势在于在对于较⼩范围内的整数排序。它的复杂度为Ο(n+k)（其中k是待排序数的最⼤值），快于任何⽐较排序算法，缺点就是⾮常消耗空间。很明显，如果⽽且当O(k)>O(n*log(n))的时候其效率反⽽不如基于⽐较的排序，⽐如堆排序和归并排序和快速排序。
算法原理：
基本思想是对于给定的输⼊序列中的每⼀个元素x，确定该序列中值⼩于x的元素的个数。⼀旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输⼊序列中只有17个元素的值⼩于x的值，则x可以直接存放在输出序列的第18个位置上。当然，如果有多个元素具有相同的值时，我们不能将这些元素放在输出序列的同⼀个位置上，在代码中作适当的修改即可。
⽤待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。
算法步骤：
（1）出待排序的数组中最⼤的元素；
（2）统计数组中每个值为i的元素出现的次数，存⼊数组C的第i项；
（3）对所有的计数累加（从C中的第⼀个元素开始，每⼀项和前⼀项相加）；
（4）反向填充⽬标数组：将每个元素i放在新数组的第C(i)项，每放⼀个元素就将C(i)减去1。
时间复杂度：Ο(n+k)。
空间复杂度：Ο(k)。
要求：待排序数中最⼤数值不能太⼤。最⼤值确定并且不⼤，必须是正整数。
稳定性：稳定。
计数排序需要占⽤⼤量空间，它仅适⽤于数据⽐较集中的情况。⽐如 [0~100]，[10000~19999] 这样的数据。
计数排序的基本思想是：对每⼀个输⼊的元素arr[i]，确定⼩于 arr[i] 的元素个数。
浮点数的基数什么意思所以可以直接把 arr[i] 放到它输出数组中的位置上。假设有5个数⼩于 arr[i]，所以 arr[i] 应该放在数组的第6个位置上。
计数排序⽤到⼀个额外的计数数组C，根据数组C来将原数组A中的元素排到正确的位置。
  通俗地理解，例如有10个年龄不同的⼈，假如统计出有8个⼈的年龄不⽐⼩明⼤（即⼩于等于⼩明的年龄，这⾥也包括了⼩明），那么⼩明的年龄就排在第8位，通过这种思想可以确定每个⼈的位置，也就排好了序。当然，年龄⼀样时需要特殊处理（保证稳定性）：通过反向填充⽬标数组，填充完毕后将对应的数字统计递减，可以确保计数排序的稳定性。
计数排序属于线性排序，它的时间复杂度远远⼤于常⽤的⽐较排序。（计数是O(n)，⽽⽐较排序不会超过O(nlog2nJ)）。
其实计数排序⼤部分很好理解的，唯⼀理解起来很蛋疼的是为了保证算法稳定性⽽做的数据累加，⼤家听我说说就知道了：
1、⾸先，先取出要排序数组的最⼤值，假如我们的数组是int[] arrayData = { 2, 4, 1, 5, 6, 7, 4, 65, 42 };，那么最⼤值就是65.（代码17-21⾏就是在查最⼤值）
2、然后创建⼀个计数数组，计数数组的长度就是我们的待排序数组长度+1。即65+1=66。计数数组的作⽤就是⽤来存储待排序数组中，数字出现的频次。 例如，4出现了两次，那么计数数组arrayCount[4]=2。 OK，现在应该明⽩为什么计数数组长度为什么是66⽽不是65了吧？ 因为为了存储0
然后再创建⼀个存储返回结果的数组，数组长度与我们的原始数据长度是相同的。（24和26⾏）
3、进⾏计数（代码29⾄31⾏）
4、将计数数组进⾏数量累计，即arrayCount[i]+=arrayCount[i-1]（代码35⾏⾄代码37⾏）。　
  ⽬的是为了数据的稳定性， 这块我其实看了许久才看懂的…再次证明我的资质真的很差劲。 我来尽⼒解释⼀下：
其实这个与后边那步结合着看理解起来应该更容易些。
例如我们计数数组分别是 1 2 1 2 1 的话，那么就代表0出现了⼀次，1出现了两次，2出现了⼀次，3出现了两次。
  这个是很容易理解的。 那我们再换个⾓度来看这个问题。
  我们可以根据这个计数数组得到每个数字出现的索引位置，即数字0出现的位置是索引0，数字1出现的问题是索引1，2；数字2出现的位置是索引3，数字4出现的位置是索引4，5。。。。
  OK，⼤家可以看到，这个索引位置是累加的，所以我们需要arrayCount[i]+=arrayCount[i-1]来存储每个数字的索引最⼤值。 这样为了后边的输出
5、最后，把原始数据从后往前输出；然后每个数字都能到计数器的最后实现索引。  然后将数字存储在实际索引的结果数组中。 然后计数数组的索引--， 结果就出来了。
PS：计数排序其实是特别吃内存的
时间复杂度：
O(n+k)
请对照下⽅代码：因为有n的循环，也有k的循环，所以时间复杂度是n+k
空间复杂度：
O(n+k)
请对照下⽅代码：需要⼀个k+1长度的计数数组，需要⼀个n长度的结果数组，所以空间复杂度是n+k
public static void main(String[] args) {
int[] arrayData = { 2, 3, 1, 5, 6, 7, 4, 65, 42 };
int[] arrayResult = CountintSort(arrayData);
}
public static int[] CountintSort(int[] arrayData) {
int maxNum = 0;
// 取出最⼤值
for (int i : arrayData) {
if (i > maxNum) {
maxNum = i;
}
}
// 计数数组
int[] arrayCount = new int[maxNum + 1];
/
/ 结果数组
int[] arrayResult = new int[arrayData.length];
// 开始计数
for (int i : arrayData) {
arrayCount[i]++;
}
// 对于计数数组进⾏ i=i+(i-1)
// ⽬的是为了保证数据的稳定性
for (int i = 1; i < arrayCount.length; i++) {
arrayCount[i] = arrayCount[i] + arrayCount[i - 1];
}
for (int i = arrayData.length - 1; i >= 0; i--) {
arrayResult[arrayCount[arrayData[i]] - 1] = arrayData[i];
arrayCount[arrayData[i]]--;
}
return arrayResult;
}
算法分析
主要思想：根据array数组元素的值进⾏排序，然后统计⼤于某元素的元素个数，最后就可以得到某元素的合适位置；⽐如：array[4] = 9；统计下⼩于array[4]的元素个数为：8；所以array[4] = 9 应该放在元素的第8个位置；
主要步骤：
1、根据array数组，把相应的元素值对应到tmpArray的位置上；
2、然后根据tmpArray数组元素进⾏统计⼤于array数组各个元素的个数；
3、最后根据上⼀步统计到的元素，为array元素到合适的位置，暂时存放到tmp数组中；
如下图所⽰：array 是待排序的数组；tmpArray 是相当于桶的概念； tmp 是临时数组，保存array排好序的数组；
注意：计数排序对输⼊元素有严格要求，因为array元素值被⽤来当作tmpArray数组的下标，所以如果array的元素值为100的话，那么tmpArray数组就要申请101（包括0，也就是 mix - min + 1）。
时间复杂度
时间复杂度可以很好的看出了就是：O( n )；
空间复杂度
空间复杂度也可以很好的看出来：O( n )；
总结
计数排序的时间复杂度和空间复杂度都是⾮常有效的，但是该算法对输⼊的元素有限制要求，所以并不是所有的排序都使⽤该算法；最好的是0～9之间的数值差不会很⼤的数据元素间⽐较；有⼈会说这个没多⼤⽤，但是在后⾯的基数排序中会看到，这可以算是基数排序中的⼀个基础；
基数排序(Radix Sort)
  基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡⽚制表机上的贡献。它是这样实现的：将所有待⽐较正整数统⼀为同样的数位长度，数位较短的数前⾯补零。然后，从最低位开始进⾏基数为10的计数排序，⼀直到最⾼位计数排序完后，数列就变成⼀个有序序列（利⽤了计数排序的稳定性）。
基数排序的时间复杂度是O(n * dn)，其中n是待排序元素个数，dn是数字位数。这个时间复杂度不⼀定优于O(n log n)，dn的⼤⼩取决于数字位的选择（⽐如⽐特位数），和待排序数据所属数据类型的全集的⼤⼩；dn决定了进⾏多少轮处理，⽽n是每轮处理的操作数⽬。
  如果考虑和⽐较排序进⾏对照，基数排序的形式复杂度虽然不⼀定更⼩，但由于不进⾏⽐较，因此其
基本操作的代价较⼩，⽽且如果适当的选择基数，dn⼀般不⼤于log n，所以基数排序⼀般要快过基于⽐较的排序，⽐如快速排序。由于整数也可以表达字符串（⽐如名字或⽇期）和特定格式的浮点数，所以基数排序并不是只能⽤于整数排序。
基数排序已经不再是⼀种常规的排序⽅式，它更多地像⼀种排序⽅法的应⽤，基数排序必须依赖于另外的排序⽅法。基数排序的总体思路就是将待排序数据拆分成多个关键字进⾏排序，也就是说，基数排序的实质是多关键字排序。
如果按照习惯思维，会先⽐较百位，百位⼤的数据⼤，百位相同的再⽐较⼗位，⼗位⼤的数据⼤；最后再⽐较个位。⼈得习惯思维是最⾼位优先⽅式。但⼀旦这样，当开始⽐较⼗位时，程序还需要判断它们的百位是否相同--这就认为地增加了难度，计算机通常会选择最低位优先法。
基数排序⽅法对任⼀⼦关键字排序时必须借助于另⼀种排序⽅法，⽽且这种排序⽅法必须是稳定的。对于多关键字拆分出来的⼦关键字，它们⼀定位于0-9这个可枚举的范围内，这个范围不⼤，因此⽤桶式排序效率⾮常好。对于多关键字排序来说，程序将待排数据拆分成多个⼦关键字后，对⼦关键字排序既可以使⽤桶式排序，也可以使⽤任何⼀种稳定的排序⽅法。
基数排序（radix sort）属于“分配式排序”（distribution sort），⼜称“桶⼦法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配⾄某些“桶”中，藉以达到排序的作⽤，
基数排序法是属于稳定性的排序，其时间复杂度为O
(nlog(r)m)，其中r为所采取的基数，⽽m为堆数，在某些时候，基数排序法的效率⾼于其它的稳定性排序法。
算法分析
主要思想：
基数排序的实现虽然有很多，但是基本思想就是把元素从个位排好序，然后再从⼗位排好序，，，，⼀直到元素中最⼤数的最⾼位排好序，那么整个元素就排好序了。
⽐如：2，22，31，1221，90，85，105
个位排序：90，31，1221，2，22，85，105
⼗位排序：2，105，1221，22，31，85，90
百位排序：2，22，31，85，90，105，1221
千位排序：2，22，31，85，90，105，1221
注意：每次排序都是在上次排序的基础上进⾏排序的，也就是说此次排序的位数上他们相对时，就不移动元素（即顺序参数上⼀个位数的排序顺序）
主要步骤：
1、把所有元素都分配到相应的桶中
2、把所有桶中的元素都集合起来放回到数组中
3、依次循环上⾯两步，循环次数为最⼤元素最⾼位数
代码分析：
参考下图
1、竖  0～9：表⽰桶个数（每个位数上的数字都在0到9之间）；
2、⾏ 0～length：0 表⽰在某个桶内有多少个元素；
3、⽐如：所有元素中个位为5的有两个元素，5 ， 95；那么在下图中存放，分别是：（5，0） = 2；（5，1） = 5；（5，2）= 95；

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。