카운트 정렬(CountingSort) Java 구현


/**
 *     
 */
public class CountingSort {

    /**
     *            0..k   
     * @param data      
     * @param k     
     * @return     
     */
    public static int[] sort(int[] data, int k) {
        //          tmp,      0;k        
        int[] tmp = new int[k + 1];

        //          i     ,    tmp   i ,          tmp      
        for (int i = 0; i <= data.length - 1; i++) {
            tmp[data[i]]++;
        }

        //                 ,  tmp         ,         
        for (int j = 1; j <= k; j++) {
            tmp[j] = tmp[j] + tmp[j - 1];
        }

        // result           
        int[] result = new int[data.length];
        for (int i = data.length - 1; i >= 0; i--) {
            result[tmp[data[i]] - 1] = data[i];
            tmp[data[i]]--;
        }

        return result;
    }
}

좋은 웹페이지 즐겨찾기