计数排序

声明： 本总结仅为个人学习总结，以防止遗忘而作，不得转载和商用。
计数排序在百度百科（https://baike.baidu.com/item/%E8%AE%A1%E6%95%B0%E6%8E%92%E5%BA%8F/8518144?fr=aladdin）是这样说的：计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。[1-2]
当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序，堆排序）
下图的例子说明了计数排序的过程

计数排序
Java代码实现如下：

package com.mystudy.algorithm;
/**
 * @desc Count Sort algorithm
 * @author 
 *
 */
public class CountSort {

    public static void main(String[] args) {
        int[] A=new int[]{2,5,3,0,2,3,0,3};
        int[] B=countSort(A, 5);
        for(int i=0;i<A.length;i++)
        {
            System.out.print((i+1)+"th:"+B[i]);
        }
    }
    /**
     * 
     * @param array 待排序数组
     * @param k 数组中的最大值
     * @return
     */
    private static int[] countSort(int[] array,int k)
    {
        int[] C=new int[k+1];//构造C数组,大小为最大值-最小值+1即例中(5-0)+1 = 6
        int length=array.length,sum=0;//获取A数组大小用于构造B数组  
        int[] B=new int[length];//构造B数组
        for(int i=0;i<length;i++)
        {
            C[array[i]]+=1;// 统计A中各元素个数，存入C数组
        }
        for(int i=0;i<k+1;i++)//修改C数组
        {
            sum+=C[i];
            C[i]=sum;    
        }
        for(int i=length-1;i>=0;i--)//遍历A数组，构造B数组
        {
            
            B[C[array[i]]-1]=array[i];//将A中该元素放到排序后数组B中指定的位置
            C[array[i]]--;//将C中该元素-1，方便存放下一个同样大小的元素
            
        }
        return B;//将排序好的数组返回，完成排序
        
    }
}

实现二参考百科的算法：

package com.mystudy.algorithm;

public class CountSort2 {

    public static void main(String[] args) {
        int a[] = {100,93,97,92,96,99,92,89,93,97,90,94,92,95};
        int b[] = countSort(a);
        for(int i:b){
            System.out.print(i + "\t");
        }
        System.out.println();
    }

    public static int[] countSort(int[] a){
        int b[] = new int[a.length];
        int max = a[0],min=a[0];
        for(int i : a){
            if (i>max) {
                max = i;
            }
            if (i<min) {
                min = i;
            }
        }
        int k = max - min + 1;//这里k的大小是要排序的数组中，元素大小的极值差+1
        int c[] = new int[k];
        for(int i=0;i<a.length;++i){
            c[a[i]-min] += 1;//优化过的地方，减小了数组c的大小
        }
        for(int i=1;i<c.length;++i){
            c[i] = c[i] + c[i-1];
        }
        for(int i=a.length-1;i>=0;--i){
            b[--c[a[i]-min]] = a[i];//按存取的方式取出c的元素
        }
        return b;
    }
}