计数排序、桶排序与基数排序详解

鸽巢原理

鸽子归巢，待排序数据归到有序组群中按大小归进有序组群来排。数越大，归到的有序组就在越后的；数越小，归到的有序组就在越前的。

• 如果有序组以一个元素一个元素划分的，实现的是元素组归巢排序，即计数排序。
• 如果有序组按范围多个元素为一组划分的，实现的是范围组归巢排序，即桶排序。

---

一、计数排序

1. 实现

1.1 步骤

1. 开辟数据范围内的所有元素都有各自对应的元素组巢穴，范围内一共有多少种个数据，就开辟每种个数据都有对应的多大的数组，比如 90(max) - 10(min) = 80(种个数据)。
2. 归巢时，通过该数据 - 数据范围内的最小值得到所归巢的下标，然后在数组元素巢中计数表示归巢。
3. 因为巢内只有一种个数据直接就是有序的，所以所有数据归完巢在巢层面有序时所有数据就已经有序了，最后将它们按顺序地赶出巢加回去即得原来有序的数据。

1.2 代码

public static void countSort(int[] array) {
    // 1. 求当前数据的最大值和最小值
    int minVal = array[0];
    int maxVal = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] < minVal) {
            minVal = array[i];
        }
        if (array[i] > maxVal) {
            maxVal = array[i];
        }
    }
    // 2. 根据数据最大值和最小值来确定元素组巢穴数组的大小
    int[] count = new int[maxVal - minVal + 1];
    // 3. 遍历原来的数据进行归巢排序
    for (int i  ; i < array.length; i++) {
        count[array[i] - minVal]++;
    }
    
       ;
     (   ; i < count.length; i++) {
         (count[i] > ) {
            array[index] = i + minVal;
            index++;
            count[i]--;
        }
    }
}