计数排序

9.计数排序

计数排序是一个非基于比较的排序算法，它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 [1] 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序，堆排序）

最坏、最好、平均时间复杂度：N+K ; 空间复杂度为：N+K

K不能省略，因为K为范围，受范围影响很大，当O(k)>O(n*log(n))时，受益低。

相关资料：https://blog.csdn.net/qq_42111463/article/details/84146915

   static int[] countSort(int[] a) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < a.length; i++) {
            max = a[i] > max ? a[i] : max;
            min = a[i] < min ? a[i] : min;
        }
        int[] help = new int[max - min + 1];
        for (int i = 0; i < a.length; i++) {
            help[a[i] - min]++;//最小的数放在下标为0的位置
        }      //////////////////////////////////////////////////////////
        //基本数据类型做法,直接输出到原数组排序;空间复杂度为K
//        int j = 0;
//        for (int i = 0; i < help.length; i++) {
//            while (help[i]-- > 0) {//当计数数组不为0时,
//                a[j++] = i + min;//将下标对应的数(i+min)依次填入原数组中
//            }
//        }
        //////////////////////////////////////////////////////////
        //对象如何保证稳定性  排名数组和新数组排序,空间复杂度:N+K
        //1.将统计数组变形为排名数组
        int sum = 0;//当前排名
        for (int i = 0; i < help.length; i++)//统计数组做变形，后面的元素等于前面元素的和,排名
        {
            sum += help[i];
            help[i] = sum;
        }
//////////////////计数数组变形为排名数组优化
//        for (int i = 1; i < help.length; i++)//统计数组做变形，后面的元素等于前面元素的排名加上自身的计数个数
//        {
//            help[i] += help[i-1];
//        }
//////////////////取数排序过程分析
        //此时将计数数组变成了排名数组,
        //再逆序输出原数组,将原数组的每一个数根据排名数组的下标去找排名,放在新数组中;
        //同时把排名数组对应位置的名次-1
        int[] sortArr = new int[a.length];
        for (int j = a.length - 1; j >= 0; j--) {
            sortArr[help[(a[j]-min)]-1]=a[j];//a[j]是原数组的数, a[j]-min是在排名数组中对应的下标,
            // help[a[j]-min]是对应的排名,help[a[j]-min]-1是在新建存放稳定数组中的存放位置
            help[(a[j]-min)]--;//同时将该下标的排名-1
        }
////////////////取数排序可以简化为一条语句
//        for(int i=a.length-1;i>=0;i--){
//            b[--c[a[i]-min]]=a[i];//按存取的方式取出c的元素
//        }
        return sortArr;//将排好序的稳定数组返回
    }
}

//优化版
  public static int[] countSort(int[]a){
    int b[] = new int[a.length];
    int max = a[0],min = a[0];
    for(int i:a){
       max = a[i] > max ? a[i] : max;
       min = a[i] < min ? a[i] : min;
      }
    }//这里k的大小是要排序的数组中，元素大小的极值差+1
    int c[]=new int[max-min+1];//初始化计数数组
    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;
  }
}