package chap08_Linear_Time_Sort;

import static org.junit.Assert.*;

import java.util.Arrays;

import org.junit.Test;

public class CopyOfSortAlgorithms {
    /**
     * 基数排序
     * 
     * @param n
     * @param digit
     */
    static void radixSort(int[] n, int digit) {
        int[] b = new int[n.length];// 临时存储数组
        int[] c = new int[10];// 用于记录各个位上的数个数
        int d = 1;// 用来记录位数，从各位到最大数的位数
        int div = 1;// 作为除数，从各位到最大位，10,100,1000,10000.....

        while (d <= digit) {
            for (int i = 0; i < n.length; i++) {
                c[(n[i] / div) % 10]++;
            }
            for (int j = 1; j < 10; j++) {
                c[j] += c[j - 1];
            }
            for (int k = n.length - 1; k >= 0; k--) {
                b[c[(n[k] / div) % 10] - 1] = n[k];
                c[(n[k] / div) % 10]--;
            }
            System.arraycopy(b, 0, n, 0, b.length);
            Arrays.fill(c, 0);
            div *= 10;
            d++;
        }
    }

    @Test
    public void testName() throws Exception {
        int[] a = { 329, 457, 657, 839, 436, 72, 35, 1 };
        System.out.println(Arrays.toString(a));
        radixSort(a, 3);
        System.out.println(Arrays.toString(a));
    }
}