第八章線形時間ソート8.2カウントソート

package chap08_Linear_Time_Sort;



import static org.junit.Assert.*;



import java.util.Arrays;



import org.junit.Test;



public class SortAlgorithms {

    /**

     *   maxvalue 

     * 

     * @param a

     * @param maxValue

     */

    static void countingSort(int[] a, int maxValue) {

        //  a 

        int[] b = Arrays.copyOf(a, a.length);

        //  0 maxvalue ， a 

        int[] c = new int[maxValue + 1];

        //  

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

            c[b[i]]++;

        }

        //  c[i] i 

        for (int i = 1; i <= maxValue; i++) {

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

        }

        //  a 。 ， 

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

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

            c[b[i]]--;

        }

    }



    @Test

    public void testName() throws Exception {

        int[] a = { 13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11 };

        System.out.println(Arrays.toString(a));

        countingSort(a, 21);

        System.out.println(Arrays.toString(a));

    }

}