排序算法 - 鸽巢排序

基本思想

鸽巢排序是桶排序的一种，顾名思义，就是一排鸽巢，看里面有几个鸽巢，然后遍历这些鸽巢，打印出来就好，排序之前得先知道区间和最大值。

比如有数组a = [2,7,5,9,8,8]，我们需要对这个数组进行排序，这是一个最大值不超过10的数组，那么我们定区间为0-10，定义一个下标0-10这样一个11位数组b,初始化值为0。然后遍历已知数组a，通过a的一项一项的值和我们定义的数组b的下标进行对应。

遍历开始：

取a[0]=2，然后操作b[2]=1

取a[1]=7，然后操作b[7]=1

取a[2]=5，然后操作b[5]=1

取a[3]=9，然后操作b[9]=1

取a[4]=8，然后操作b[8]=1

取a[5]=8，然后操作b[8]=2（注意了哦）

这样就对号入座了，之后遍历b，如果b中某个小标对应的值是多个，则遍历多次，把不是0的给打印出来，结果就是我们想要的了

代码

package main.java.com.study.sortingAalgorithm;

import main.java.com.study.utils.CommonUtils;

/**
 * @author: whb
 * @description: 鸽巢排序
 * 原理类似桶排序,同样需要一个很大的鸽巢[桶排序里管这个叫桶,名字无所谓]
 * 鸽巢其实就是数组,数组的索引位置就表示值,该索引位置的值表示出现次数,如果全部为1次或0次那就是桶排序
 * 例如
 * int[] pigeonHole = new int[100];
 * pigeonHole[0]的值表示0的出现次数...
 * pigeonHole[1]的值表示1的出现次数...
 * pigeonHole[2]的值表示2的出现次数...
 */
public class PigeonholeSort {

    /**
     * 鸽巢排序
     *
     * @param unsorted  待排序列
     * @param maxNumber 最大数
     * @return
     */
    public static int[] pigeonholeSort(int[] unsorted, int maxNumber) {
        int[] pogeonHole = new int[maxNumber + 1];
        for (int item : unsorted) {
            pogeonHole[item]++;
        }
        return pogeonHole;
    }

    public static void main(String[] args) {
        int[] unsorted = {99, 65, 24, 47, 47, 50, 99, 88, 66, 33, 66, 67, 31, 18, 24};
        System.out.println("**************鸽巢排序******************");
        System.out.println("排序前：");
        CommonUtils.display(unsorted);
        int[] sorted = pigeonholeSort(unsorted, 99);
        System.out.println("排序后：");
        for (int i = 0; i < sorted.length; i++) {
            for (int j = 0; j < sorted[i]; j++) {
                System.out.print(i + "  ");
            }
        }
    }
}

测试结果