实现字符串计数排序时遇到的问题

Question

html prettyprint-override">import java.util.Arrays;

public class StringCountSort{
    
    public static void countingSort(String[] array, int size, int digit)
    {

        String[] result = new String[size+1];
        
        int maximum = 122;
        
        int[] count = new int[maximum + 1];
        for (int i = 0; i < count.length; i++){
            count[i] = 0;
        }
        
        for (int i = 0; i < size; i++){
            count[array[i].charAt(digit)] +=1;
        }
        
        for (int i = 1; i < count.length; i++){
            count[i] += count[i-1];
        }
    
        for (int i = size -1; i >= 0; i--){

            result[count[array[i].charAt(digit)] - 1] = array[i];
            count[array[i].charAt(0)]--;
        }

        for (int i = 0; i < size; i++) {
            array[i] = result[i];
        }
    }
    
    public static void main(String args[]){
        String[] data = { "eg", "fa", "bz", "ch", "hv", "df", "ag" };
        StringCountSort.countingSort(data, data.length, 1);
        System.out.println("Sorted Array in Ascending Order: ");
        System.out.println(Arrays.toString(data));
        
        
        
    }
}

line 28 result[count[array[i].charAt(digit)] - 1] = array[i]; 

line 37 StringCountSort.countingSort(data, data.length, 1); 

Answer 1

改变

count[array[i].charAt(0)]--;

到

count[array[i].charAt(digit)]--;

这应该能奏效。

null

    public static void countingSort(String[] array, int digit) {
        String[] result = new String[array.length];
        int[] count = new int[Character.MAX_VALUE + 1];

        for (int i = 0; i < array.length; i++){
            count[array[i].charAt(digit)]++;
        }
        for (int i = 1; i < count.length; i++){
            count[i] += count[i-1];
        }
        for (int i = array.length -1; i >= 0; i--){
            result[count[array[i].charAt(digit)] - 1] = array[i];
            count[array[i].charAt(digit)]--;
        }
        for (int i = 0; i < array.length; i++) {
            array[i] = result[i];
        }
    }