CountingSort and RadixSort

CountingSort

/**
 * counting sort is stable
 * 他保证了在排序的过程中元素的相对位置不会变化
 * radix sort也正是利用了这一点,所以radix sort也是stable
 * @author haofan.whf
 * @version $Id: CountSort.java, v 0.1 2018年12月24日 10:30 haofan.whf Exp $
 */
public class CountingSort {

    public static void main(String args[]){

        int[] array = ArrayUtils.randomArray(10);

        int[] sortedArray = sort(array);

        for (int i = 0; i < sortedArray.length; i++) {
            System.out.println(sortedArray[i]);
        }
        ArrayUtils.checkIfSorted(sortedArray, true);
    }

    /**
     * T(n) = O(n + k)
     * k=count.length
     * 该算法的时间复杂度和K的取值密切相关
     * 当k=n时,该排序算法的时间复杂度为O(n)
     * 但设想当k=n^2的时候,该算法的时间复杂度就是O(n^2)
     * @param array
     * @return
     */
    public static int[] sort(int[] array){
        int max = ArrayUtils.findMax(array);
        int[] count = new int[max + 1];
        for (int i = 0; i < array.length; i++) {
            count[array[i]] ++ ;
        }
        int[] offset = new int[count.length];
        offset[0] = 0;
        for (int i = 1; i < offset.length; i++) {
            offset[i] = offset[i - 1] + count[i - 1];
        }
        int[] sortedArray = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            sortedArray[offset[array[i]] ++] = array[i];
        }
        return sortedArray;
    }

}

RadixSort

/**
 *
 * @author haofan.whf
 * @version $Id: RadixSort.java, v 0.1 2018年12月25日 09:57 haofan.whf Exp $
 */
public class RadixSort {

    /**
     * T(n) = O(n)
     * radix sort是把数字从位的角度来看
     * 比如
     * 1234 = 1,2,3,4
     * 1    = 0,0,0,1
     * 23   = 0,0,2,3
     * radix sort 会从最低位开始比较直到最高位
     * 每次比较都使用counting sort
     * 我们假设以10为底,其中最大的数为x,那么需要进行d=lg(x)次counting sort
     * T(n) = d * T(n + k) = T(dn + dk)
     * 如果要让radix sort时间复杂度最低
     * 那么d=O(1)使得dn=O(n)
     * dk如果时间复杂度大于dn则没有意义，那么dk最大只能是O(n)
     * 则推导出当k=O(n)时,T(n)=O(n)
     * @param array
     * @return
     */
    public static void sort(int[] array){
        int max = ArrayUtils.findMax(array);

        int exp = 10;
        for (int i = 1; max / i > 0; i *= exp) {
            int[] digits = new int[array.length];
            for (int j = 0; j < digits.length; j++) {
                digits[j] = (array[j] / i) % exp;
            }

            array = countingSort(array, digits);

        }

        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }

        ArrayUtils.checkIfSorted(array, true);

    }
    
    private static int[] countingSort(int[] array, int[] digits){
        int max = ArrayUtils.findMax(digits);
        int[] offset = new int[max + 2];
        offset[max + 1] = digits.length;
        for (int i = 0; i < digits.length; i++) {
            offset[digits[i]] ++;
        }
        for (int i = offset.length - 2; i >= 0; i--) {
            offset[i] = offset[i + 1] - offset[i];
        }
        int[] output = new int[array.length];
        for (int i = 0; i < digits.length; i++) {
            output[offset[digits[i]] ++ ] = array[i];
        }
        return output;
    }

    public static void main(String args[]){
        int[] array = ArrayUtils.randomArray(1000);

        sort(array);
    }
}