Counting Sort(Java)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

 public static void countingsort(int[] a, int n) //n = a.length

 {

     int max = a[0], min = a[0];

     for(int i = 1; i < a.length; i++)

     {

     if(a[i] > max)

         max = a[i];

     if(a[i] < min)

         min = a[i];

     }

     int[] b = new int[max - min + 1];

     int[] c = new int[n];

     //获取频数

     for(int i = 0; i < a.length; i++)

     b[a[i] - min]++;

     //得到a数组中每个元素的位置

     for(int i = 1; i < b.length; i++)

         b[i] += b[i - 1];

     //逆序遍历a数组 保证计数排序是稳定的

     for(int i = a.length - 1; i >= 0; i--)

     {

     c[b[a[i] - min] - 1] = a[i];

     b[a[i] - min]--;

     }

     for(int i  = 0; i < a.length; i++)

     a[i] = c[i];

 }