Код сортировки LSD Radix в Java - PullRequest
0 голосов
/ 11 июня 2010

Я готовлюсь к экзамену, который будет посвящен алгоритмам сортировки.Друг дал мне этот код о сортировке по радиоканалу ЛСД, и я не понимаю, почему он использует номера 96,97 и 64?Я прочитал несколько вещей о сортировке LSD радикс, но я не понял, как это работает.

public class LSDRadix {
    private static String[] list;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine().trim());

        int size=0;
        list =new String[n];

        for(int i=0; i<n; i++){
            list[i]= sc.nextLine();

            if(size < list[i].length()){
                size = list[i].length();
            }
        }
        sort(size);

        for(int j=0; j<n;j++)
            System.out.println(list[j]);
    }

    private static void sort(int sizes){
        int numChars = 58;
        String [] aux = new String[list.length];
        int[] counter;

        for(int i=sizes-1; i>=0 ;i--){       
            counter = new int[numChars];

            for(int j=0; j<list.length; j++){
                if(list[j].length() > i){
                    if(list[j].charAt(i) >= 97)
                        counter[list[j].charAt(i)-96]++;
                    else
                        counter[list[j].charAt(i)-64]++;
                }else{
                    counter[0]++;
                }
            }

            for(int j=0; j<numChars-1; j++){
                counter[j+1] += counter[j]; 
            }

            for(int j=list.length-1; j>=0; j--){
                if(list[j].length() > i){
                    int pos;
                    if(list[j].charAt(i) >= 97){
                        pos = list[j].charAt(i)-96;
                    }else{
                        pos = list[j].charAt(i)-64;
                    }
                    aux[counter[pos]-1] = list[j];
                    counter[pos]--;
                }else{
                    aux[counter[0]-1] = list[j];
                    counter[0]--;
                }
            }

            for(int j=0; j<list.length; j++){
                list[j] = aux[j];
            }
        }   
    }
}

1 Ответ

4 голосов
/ 11 июня 2010

97 - это значение ASCII для буквы «а». Если тестируемый символ представляет собой строчную букву, вычитание 96 из его значения ASCII даст число от 1 до 26.

В противном случае символ считается заглавной буквой. 65 - значение ASCII для буквы «A», поэтому вычитание 64 снова даст значение от 1 до 26.

...