计数排序

比较计数


比较计数的思想就是算出列表中小于该元素个数，并把结果记录在一张表，在根据表，指出元素在有序表的位置






比较计数的思想确实很简单，接下来，看它的实现代码吧




[java] view plaincopyprint?
/** 
 * 比较排序 
 * @author chenxuegui 
 * 
 */  
public class CompareCountSort  
{  
    public static void main(String[] args)  
    {  
        int[] a = new int[] { 62, 31, 84, 96, 19, 47 };  
  
        a = compareCountSort(a);  
  
        for (int i : a)  
        {  
            System.out.print(i + " ");  
        }  
  
    }  
  
    /** 
     * 比较排序 
     *  
     * @param a 
     */  
    private static int[] compareCountSort(int[] a)  
    {  
        int[] count = new int[a.length];  
  
        // 计算每个元素中在当前数组的位置  
        for (int i = 0; i < a.length; i++)  
        {  
            for (int j = i + 1; j < a.length; j++)  
            {  
                if (a[i] > a[j])  
                {  
                    count[i]++;  
                }  
                else  
                {  
                    count[j]++;  
                }  
            }  
        }  
  
        int[] result = new int[a.length];  
        // 根据位置对元素进行迁移  
        for (int i = 0; i < a.length; i++)  
        {  
            result[count[i]] = a[i];  
        }  
  
        return result;  
    }  
}  


该算法的效率为O(n^2)，比较次数和选择排序一样多，并且还占用线性数量的额外空间，所以该算法是不推荐的。但是，当情况变成只对几个数进行统计，那该算法就很有意义了，那就是分布计数了




分布计数


分布计数其实和比较计数没什么太大区别，只是他是特定场景下的一种应用


比如如考虑是数据情况是 2，3，4的交叉进行排序，如 2  4  3  3 4 2 4 2 3 4 2 3 2 3 4




好吧，下面看一下他的实现代码




[java] view plaincopyprint?
/** 
 * 分布排序 
 *  
 * @author chenxuegui 
 *  
 */  
public class DistributionCounting  
{  
    public static void main(String[] args)  
    {  
        int[] a = new int[] { 2,3,2,4,4,3,2,3,4,3,4,2,4};  
  
        a = distributionCounting(a, 2, 4);  
  
        for (int i : a)  
        {  
            System.out.print(i + " ");  
        }  
  
    }  
  
    /** 
     * 分布排序核心 
     *  
     * @param a 
     * @param low 
     *            数组数值下限 
     * @param high 
     *            数组数值上限 
     */  
    private static int[] distributionCounting(int[] a, int low, int high)  
    {  
        int count[] = new int[high - low + 1];  
  
        // 统计每个的次数  
        for (int i = 0; i < a.length; i++)  
        {  
            count[a[i] - low]++;  
        }  
  
        // 重用于分布  
        for (int i = 1; i < count.length; i++)  
        {  
            count[i] += count[i - 1];  
        }  
  
        int[] result = new int[a.length];  
        int index;  
  
        // 根据位置进行排序  
        for (int i = 0; i < a.length; i++)  
        {  
            index = a[i] - low;  
  
            result[--count[index]] = a[i];  
        }  
  
        return result;  
    }  
}  


这是一个线性算法，效率比合并、快排效率还要高