算法说明
鸽巢排序是分布排序的一种，我理解其实鸽巢就是计数排序的简化版，不同之处就是鸽巢是不稳定的，计数排序是稳定的。
逻辑很简单，就是先找出待排数组的最大值maxNum，然后实例一个maxNum+1长度的数组。
例如待排数组int[] arrayData = { 22, 33, 57, 55, 58, 77, 44, 65, 58, 42 };
最大值是77.然后实例一个int[] arrayTemp = new int[77]的数组。
然后呢，循环arrayData。然后第一个数字是22， 那么arrayTemp[22]++。
然后第二个数字是33，那么arrayTemp[33]++。
接着arrayTemp[57]++
arrayTemp[55]++
.....
...
最后arrayTemp[42]++
最后将arrayTemp数组输出至原始数组中，那么原始数组就是排序后的数组了。
很easy吧！
代码
使用的是java
package hark.sort.distributionsort; /*
* 鸽巢排序
*/
public class PigeonholeSort {
public static void main(String[] args) {
int[] arrayData = { 22, 33, 57, 55, 58, 77, 44, 65, 58, 42 };
PigeonhomeSortMethod(arrayData);
for (int integer : arrayData) {
System.out.print(integer);
System.out.print(" ");
}
} public static void PigeonhomeSortMethod(int[] arrayData) {
int maxNum = 0;
for (int i = 0; i < arrayData.length; i++) {
if (arrayData[i] > maxNum) {
maxNum = arrayData[i];
}
} int[] arrayTemp = new int[maxNum + 1];
for (int i = 0; i < arrayData.length; i++) {
arrayTemp[arrayData[i]]++;
} int index = 0;
for (int i = 0; i < maxNum + 1; i++) {
for (int j = 0; j < arrayTemp[i]; j++) {
arrayData[index++] = i;
}
}
}
}
参考