排序算法<No.1> 【计数排序】

继上篇博文，今天我将先介绍一下什么是计数排序，将计数排序描述清楚后，再进行后续的桶排序方法解决这个问题。

通常情况下，一提到排序，大家第一反应就是比较，其实，今天我要说的这个计数排序，不是基于比较的排序算法。

计数排序的主要思路（精髓）：

针对给定的一组整数数据，在其中任意选取一个数X，统计出这组数中不比X大的所有数据的个数n，那么，此时，X的大小次序就应该在这组数的n+1的位置了。

针对这个思想，有几点要注意：

1. 给定的数组A的数据，必须都是整数

2. 给定的数据比较稀疏的情况下，效率（空间）比较差

计数排序的处理逻辑，分为下面几步：

1. 找出输入数组A中的最小值min，以及最大值max，求出数组A的元素最大距离k = max - min + 1；

2. 初始化计数数组C，其数组长度为K；

3. 统计数组A中每个元素A[i]与最小值min的差值作为C数组的下标对应的元素的个数；

4. 计算出C数组中每个元素C[j]及其之前所有元素的和作为当前元素C[j]的新值；

5. 初始化输出数组B，其长度和输入数组A的长度一样；

6. 对数组A进行倒序的方式，将数组A的元素基于其元素的个数排位，进行对输出数组赋值，其中，考虑输入元素中有重复元素的情况；

理论比较的晦涩吧，那么先上代码吧，下面是JAVA代码实现的计数排序：

/**
 * @author "shihuc"
 * @date   2017年1月16日
 */
package jishuSort;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

/**
 * @author chengsh05
 *
 */
class InnerMaxMin {
    int max;
    int min;
    /**
     * @return the max
     */
    public int getMax() {
        return max;
    }
    /**
     * @param max the max to set
     */
    public void setMax(int max) {
        this.max = max;
    }
    /**
     * @return the min
     */
    public int getMin() {
        return min;
    }
    /**
     * @param min the min to set
     */
    public void setMin(int min) {
        this.min = min;
    }
}
public class CountSortDemo {

    /**
     * @param args
     */
    public static void main(String[] args) {
        File file = new File("./src/jishuSort/sampleCount.txt");
        Scanner sc = null;
        try {
            sc = new Scanner(file);
            int N = sc.nextInt();
            for(int i=0; i<N; i++){
                int S = sc.nextInt();
                int A[] = new int[S];
                for(int j=0; j<S; j++){
                    A[j] = sc.nextInt();
                }                    
                int B[] = countSortResult(A);
                printResult(B);
            }
        } catch (FileNotFoundException e) {            
            e.printStackTrace();
        } finally {
            if(sc != null){
                sc.close();
            }
        }
    }
    
    /**
     * 在时间复杂度为O(n)情况下，计算出最大值与最小值
     * 
     * @param da
     * @return
     */
    public static InnerMaxMin getMaxMin(int da[]){
        InnerMaxMin mm = new InnerMaxMin();
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i=0; i<da.length; i++){
            if(da[i] > max){
                max = da[i];
            }
            if(da[i] < min){
                min = da[i];
            }
        }
        
        mm.setMax(max);
        mm.setMin(min);
        return mm;
    }
    
    /**
     * 获取最大值与最小值之间的距离 k
     * 计算逻辑步骤1
     * 
     * @param mm
     * @return k
     */
    public static int getDistance(InnerMaxMin mm){
        return mm.getMax() - mm.getMin() + 1;
    }
    
    /**
     * 获取转换后的计数数组C，然后将转换后的计数数组C进行计数。 此步骤的好处，是可以减少计数数组的空间开销，掐头和掐尾。
     *
     * 
     * @param A 原数组
     * @param mm 最大最小值对象
     * @return 差值数组
     */
    public static int[] getCountArray(int A[], InnerMaxMin mm){
        int K = getDistance(mm);
        int min = mm.getMin();
        
        /*
         * 初始化计数数组C。
         * 计算逻辑步骤2
         */
        int C[] = new int[K];
        Arrays.fill(C, 0); 
        
        /*
         * 计算出每个输入数组A中的元素自生的个数，主要考虑的是有重复的情况，所以先单独计算出每个元素自己一共出现了多少次。
         * 计算逻辑步骤3
         */
        for(int i=0; i<A.length; i++){
            int n = A[i];
            C[n - min]++; 
        }
        
        /*
         * 用到了最简单的动态规划思路，统计原始输入数组A中比X元素小的所有元素的个数之和
         * 计算逻辑步骤4
         */
        for(int j=1; j<C.length; j++){
            C[j] = C[j] + C[j - 1];
        }        
        
        return C;
    }
    
    /**
     * 计数排序的总入口函数
     * 
     * @param A
     * @return
     */
    public static int[] countSortResult(int A[]){
        /*
         * 初始化计数数组的输出数组B。
         * 计算逻辑步骤5
         */
        int B[] = new int[A.length];
        InnerMaxMin mm = getMaxMin(A);
        int C[] = getCountArray(A, mm);
        int min = mm.getMin();
        
        /*
         * 将输入元素基于其每个元素对应的计数个数排序操作，映射到相应的输出数组B的位置上。
         * （对于输入数组元素中不比X元素大的元素的个数为n，那么X在排序后的输出数组中的位置为n+1）
         * 计算逻辑步骤6
         */
        for(int i = A.length - 1; i>=0; i--){
            B[C[A[i] - min] - 1] = A[i];
            C[A[i] - min]--;
        }
        return B;
    }
    
    /**
     * 显示最终排序后的结果
     * 
     * @param B
     */
    public static void printResult(int B[]){
        for(int i=0; i<B.length; i++){
            System.out.print(B[i] + "  ");
        }
        System.out.println();
    }
    
}

下面也附带上我的测试数据：

3
7
2 6 3 4 5 10 9
5
2 3 1 4 6
10
2 3 1 4 6 1 15 11 7 6

也附带上测试后的结果：

2  3  4  5  6  9  10  
1  2  3  4  6  
1  1  2  3  4  6  6  7  11  15 

这个算法，是稳定的算法，性能往往比常规的比较排序要好，但是使用场景也是受限的，即参与排序的元素必须是整数，且最好不要是稀疏数组。另外，计数排序的空间消耗，相比比较排序要高。 理解计数排序的核心思想中的计算的精髓，那么这个算法就理解了。结合代码，进行理解，还是不那么难的。