我的《恋上数据结构》源码（第1季 + 第2季）：https://github.com/szluyu99/Data_Structure_Note

经典的十大排序算法！

前言

请==务必==看一下这个：排序算法前置知识+代码环境准备。

当上面的内容都准备好以后，那就开始计数排序吧！

计数排序-简单实现

之前学习的冒泡、选择、堆、插入、归并、快速、希尔排序都是基于比较的排序。

计数排序、桶排序、基数排序，都不是基于比较的排序。

• 它们是典型的用空间换时间，在某些时候，平均时间复杂度可以比 O(nlogn) 更低

计数排序于1954年由Harold H. Seward提出，适合 对一定范围内的==整数== 进行排序。

计数排序的核心思想：

• 统计每个整数在序列中出现的次数，进而推导出每个整数在有序序列中的索引

实现步骤

思路：

• 首先找出要排序数组的中的最大值 max；
• 根据最大值 max 开辟 max + 1 空间的数组 counts；
• counts 数组统计每个整数出现的次数；

• 根据整数出现的次数，对整数进行排序：

  • 遍历 counts 数组，索引index即为元素值，counts[index] 为元素的出现次数
  • 将 counts[index] 个 index 依次放入数组，即为排序过的序列

例如对 { 7, 3, 5, 8, 7, 4, 5 } 进行计数排序：max = 8

• counts 数组为 [0, 0, 0, 1, 1, 2, 1, 2, 1]
• 对 index = 3, counts[index] = 1，即往新数组中放入 1 个 3
  此时新数组为 [3]
• 对 index = 4, counts[index] = 1，即往新数组中放入 1 个 4
• 此时新数组为 [3, 4]
• 对 index = 5, counts[index] = 2，即往新数组中放入 2 个 5
• 此时新数组为 [3, 4, 5, 5]
• 对 index = 6, counts[index] = 1，即往新数组中放入 1 个 6
  此时新数组为 [3, 4, 5, 5, 6]
• 对 index = 7, counts[index] = 2，即往新数组中放入 2 个 7
  此时新数组为 [3, 4, 5, 5, 6, 7, 7]
• 对 index = 8, counts[index] = 1，即往新数组中放入 1 个
  此时新数组为 [3, 4, 5, 5, 6, 7, 7, 8]

代码实现与缺点

/**
 * 计数排序最简单的实例
 */
private void sort0(){
    // 找出最大值
    int max = array[0];
    for(int i = 1; i < array.length; i++){
        if(array[i] > max){
            max = array[i];
        }
    }
    // 根据最大值来开辟内存空间
    int[] counts = new int[max + 1];
    // 统计每个整数出现的次数
    for(int i = 0; i < array.length; i++){
        counts[array[i]]++;
    }
    // 根据整数出现的次数，对整数进行排序
    int index = 0;
    for(int i = 0; i < counts.length; i++){
        while(counts[i]-- > 0){
            array[index++] = i;
        }
    }
}

这个版本的实现存在以下问题

• 无法对负整数进行排序
• 极其浪费内存空间
• 是个不稳定的排序
• ......

计数排序 – 改进

改进思路是求出最小值。

改进-图解

每个元素累加上其前面的所有元素得到的就是元素在有序序列中的位置信息。

例如对 { 7, 3, 5, 8, 6, 7, 4, 5 } 进行改进过的计数排序：min = 3，max = 8
newArray 为新开辟的数组，newArray = [0, 0, 0, 0, 0, 0, 0, 0]，用来存放排序结果。

• counts = [1, 2, 4, 5 ,7, 8]；

元素 5 在有序序列中的的索引：counts[5 - 3] - 1 = counts[2] - 1 = 3
newArray[3] = 5; 此时 newArray = [0, 0, 0, 5, 0, 0, 0, 0]
counts[2]--;

• counts = [1, 2, 3, 5 ,7, 8]；

元素 4 在有序序列中的的索引：counts[4 - 3] - 1 = counts[1] - 1 = 1
newArray[1] = 4; 此时 newArray = [0, 4, 0, 5, 0, 0, 0, 0]
counts[1]--;

• counts = [1, 1, 3, 5 ,7, 8]；

元素 7 在有序序列中的的索引：counts[7 - 3] - 1 = counts[4] - 1 = 6
newArray[6] = 7; 此时 newArray = [0, 4, 0, 5, 0, 0, 7, 0]
counts[4]--;

• counts = [1, 1, 3, 5 ,6, 8]；

元素 6 在有序序列中的的索引：counts[6 - 3] - 1 = counts[3] - 1 = 4
newArray[4] = 6; 此时 newArray = [0, 4, 0, 5, 6, 0, 7, 0]
counts[3]--;

• counts = [1, 1, 3, 4 ,6, 8]；
  元素 8 在有序序列中的的索引：counts[8 - 3] - 1 = counts[5] - 1 = 7
  newArray[7] = 8; 此时 newArray = [0, 4, 0, 5, 6, 0, 7, 8]

counts[5]--;

• counts = [1, 1, 3, 4 ,6, 7]；

元素 5 在有序序列中的的索引： counts[5 - 3] -1 = counts[2] - 1 = 2
newArray[2] = 5; 此时 newArray = [0, 4, 5, 5, 6, 0, 7, 8]
counts[2]--;

• counts = [1, 1, 2, 4 ,6, 7]；

元素 3 在有序序列中的的索引：counts[3 - 3] - 1 = counts[0] - 1 = 0
newArray[0] = 3; 此时 newArray = [3, 4, 5, 5, 6, 0, 7, 8]
counts[0]--;

• counts = [0, 1, 2, 4 ,6, 7]；

元素 7 在有序序列中的的索引：counts[7 - 3] - 1 = counts[4] - 1 = 5
newArray[5] = 8; 此时 newArray = [3, 4, 5, 5, 6, 7, 7, 8]
counts[5]--;

改进-实现

/**
 * 计数排序
 */
public class CountingSort extends Sort<Integer>{
    
    @Override
    protected void sort() {
        // 找出最值
        int max = array[0];
        int min = array[0];
        for(int i = 0; i < array.length; i++){
            if(array[i] < min){
                min = array[i];
            }
            if(array[i] > max){
                max = array[i];
            }
        }
        // 开辟内存空间，存储次数
        int[] counts = new int[max - min + 1];
        // 统计每个整数出现的次数
        for(int i = 0; i < array.length; i++){
            counts[array[i] - min]++;
        }
        // 累加次数
        for(int i = 1; i < counts.length; i++){
            counts[i] += counts[i - 1];
        }
        // 从后往前遍历元素，将它放到有序数组中的合适位置
        int[] newArray = new int[array.length];
        for(int i = array.length - 1; i >= 0; i--){
            newArray[--counts[array[i] - min]] = array[i];
        }
        // 将有序数组赋值到array
        for (int i = 0; i < newArray.length; i++) {
            array[i] = newArray[i];
        }
    }
    
}

复杂度与稳定性

• 最好、最坏、平均时间复杂度：O(n + k)
• 空间复杂度：O(n + k)
• k 是整数的取值范围
• 计数排序属于稳定排序

计数排序-对自定义对象进行排序

如果自定义对象可以提供用以排序的整数类型，依然可以使用计数排序

private static class Person {
    int age;
    String name;
    Person(int age, String name) {
        this.age = age;
        this.name = name;
    }
    @Override
    public String toString() {
        return "Person [age=" + age 
                + ", name=" + name + "]";
    }
}

public static void main(String[] args) {
    Person[] persons = new Person[] {
            new Person(20, "A"),
            new Person(-13, "B"),
            new Person(17, "C"),
            new Person(12, "D"),
            new Person(-13, "E"),
            new Person(20, "F")
    };
    // 找出最值
    int max = persons[0].age;
    int min = persons[0].age;
    for (int i = 1; i < persons.length; i++) {
        if (persons[i].age > max) {
            max = persons[i].age;
        }
        if (persons[i].age < min) {
            min = persons[i].age;
        }
    }
    // 开辟内存空间，存储次数
    int[] counts = new int[max - min + 1];
    // 统计每个整数出现的次数
    for (int i = 0; i < persons.length; i++) {
        counts[persons[i].age - min]++;
    }
    // 累加次数
    for (int i = 1; i < counts.length; i++) {
        counts[i] += counts[i - 1];
    }
    // 从后往前遍历元素，将它放到有序数组中的合适位置
    Person[] newArray = new Person[persons.length];
    for (int i = persons.length - 1; i >= 0; i--) {
        newArray[--counts[persons[i].age - min]] = persons[i];
    }
    // 将有序数组赋值到array
    for (int i = 0; i < newArray.length; i++) {
        persons[i] = newArray[i];
    }
        
    for (int i = 0; i < persons.length; i++) {
        System.out.println(persons[i]);
    }
}

排序结果：

Person [age=-13, name=B]
Person [age=-13, name=E]
Person [age=12, name=D]
Person [age=17, name=C]
Person [age=20, name=A]
Person [age=20, name=F]