• 排序算法<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代码实现的计数排序:

      1 /**
      2  * @author "shihuc"
      3  * @date   2017年1月16日
      4  */
      5 package jishuSort;
      6 
      7 import java.io.File;
      8 import java.io.FileNotFoundException;
      9 import java.util.Arrays;
     10 import java.util.Scanner;
     11 
     12 /**
     13  * @author chengsh05
     14  *
     15  */
     16 class InnerMaxMin {
     17     int max;
     18     int min;
     19     /**
     20      * @return the max
     21      */
     22     public int getMax() {
     23         return max;
     24     }
     25     /**
     26      * @param max the max to set
     27      */
     28     public void setMax(int max) {
     29         this.max = max;
     30     }
     31     /**
     32      * @return the min
     33      */
     34     public int getMin() {
     35         return min;
     36     }
     37     /**
     38      * @param min the min to set
     39      */
     40     public void setMin(int min) {
     41         this.min = min;
     42     }
     43 }
     44 public class CountSortDemo {
     45 
     46     /**
     47      * @param args
     48      */
     49     public static void main(String[] args) {
     50         File file = new File("./src/jishuSort/sampleCount.txt");
     51         Scanner sc = null;
     52         try {
     53             sc = new Scanner(file);
     54             int N = sc.nextInt();
     55             for(int i=0; i<N; i++){
     56                 int S = sc.nextInt();
     57                 int A[] = new int[S];
     58                 for(int j=0; j<S; j++){
     59                     A[j] = sc.nextInt();
     60                 }                    
     61                 int B[] = countSortResult(A);
     62                 printResult(B);
     63             }
     64         } catch (FileNotFoundException e) {            
     65             e.printStackTrace();
     66         } finally {
     67             if(sc != null){
     68                 sc.close();
     69             }
     70         }
     71     }
     72     
     73     /**
     74      * 在时间复杂度为O(n)情况下,计算出最大值与最小值
     75      * 
     76      * @param da
     77      * @return
     78      */
     79     public static InnerMaxMin getMaxMin(int da[]){
     80         InnerMaxMin mm = new InnerMaxMin();
     81         int max = Integer.MIN_VALUE;
     82         int min = Integer.MAX_VALUE;
     83         for(int i=0; i<da.length; i++){
     84             if(da[i] > max){
     85                 max = da[i];
     86             }
     87             if(da[i] < min){
     88                 min = da[i];
     89             }
     90         }
     91         
     92         mm.setMax(max);
     93         mm.setMin(min);
     94         return mm;
     95     }
     96     
     97     /**
     98      * 获取最大值与最小值之间的距离 k
     99      * 计算逻辑步骤1
    100      * 
    101      * @param mm
    102      * @return k
    103      */
    104     public static int getDistance(InnerMaxMin mm){
    105         return mm.getMax() - mm.getMin() + 1;
    106     }
    107     
    108     /**
    109      * 获取转换后的计数数组C,然后将转换后的计数数组C进行计数。 此步骤的好处,是可以减少计数数组的空间开销,掐头和掐尾。
    110      *
    111      * 
    112      * @param A 原数组
    113      * @param mm 最大最小值对象
    114      * @return 差值数组
    115      */
    116     public static int[] getCountArray(int A[], InnerMaxMin mm){
    117         int K = getDistance(mm);
    118         int min = mm.getMin();
    119         
    120         /*
    121          * 初始化计数数组C。
    122          * 计算逻辑步骤2
    123          */
    124         int C[] = new int[K];
    125         Arrays.fill(C, 0); 
    126         
    127         /*
    128          * 计算出每个输入数组A中的元素自生的个数,主要考虑的是有重复的情况,所以先单独计算出每个元素自己一共出现了多少次。
    129          * 计算逻辑步骤3
    130          */
    131         for(int i=0; i<A.length; i++){
    132             int n = A[i];
    133             C[n - min]++; 
    134         }
    135         
    136         /*
    137          * 用到了最简单的动态规划思路,统计原始输入数组A中比X元素小的所有元素的个数之和
    138          * 计算逻辑步骤4
    139          */
    140         for(int j=1; j<C.length; j++){
    141             C[j] = C[j] + C[j - 1];
    142         }        
    143         
    144         return C;
    145     }
    146     
    147     /**
    148      * 计数排序的总入口函数
    149      * 
    150      * @param A
    151      * @return
    152      */
    153     public static int[] countSortResult(int A[]){
    154         /*
    155          * 初始化计数数组的输出数组B。
    156          * 计算逻辑步骤5
    157          */
    158         int B[] = new int[A.length];
    159         InnerMaxMin mm = getMaxMin(A);
    160         int C[] = getCountArray(A, mm);
    161         int min = mm.getMin();
    162         
    163         /*
    164          * 将输入元素基于其每个元素对应的计数个数排序操作,映射到相应的输出数组B的位置上。
    165          * (对于输入数组元素中不比X元素大的元素的个数为n,那么X在排序后的输出数组中的位置为n+1)
    166          * 计算逻辑步骤6
    167          */
    168         for(int i = A.length - 1; i>=0; i--){
    169             B[C[A[i] - min] - 1] = A[i];
    170             C[A[i] - min]--;
    171         }
    172         return B;
    173     }
    174     
    175     /**
    176      * 显示最终排序后的结果
    177      * 
    178      * @param B
    179      */
    180     public static void printResult(int B[]){
    181         for(int i=0; i<B.length; i++){
    182             System.out.print(B[i] + "  ");
    183         }
    184         System.out.println();
    185     }
    186     
    187 }

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

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

    也附带上测试后的结果:

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

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

  • 相关阅读:
    Testlink1.9.17使用方法( 第三章 初始配置[配置用户、产品] )
    Testlink1.9.17使用方法(第二章 登录&汉化设置)
    Testlink1.9.17使用方法(第一章 前言)
    TestLink-Windows安装教程
    Linux-Redmine安装方法
    怎么使用Fiddler进行抓包
    配置ADB到Windows环境变量
    Android获取定位权限,获取设备所在的经纬度
    Paint.FontMetrics
    Bitmap上下合成图片
  • 原文地址:https://www.cnblogs.com/shihuc/p/6288844.html
一二三 - 开发者的网上家园