Радиксиальный алгоритм Понимание в Java

Question

Ниже приведен код для алгоритма radix с сайта www.sanfoundry.com. Я не понимаю третий цикл loop in while: почему int i нужно пересчитывать обратно и как этот цикл работает, чтобы отменить упорядоченные элементы до b []. И еще один вопрос: что, если мы будем считать число, основанное на 2, следуя аналогичному коду? И есть ли возможность изменить этот код для смешивания положительных и отрицательных чисел?

public static void radixSort(int[] input){ 
    final int N = input.length; 
    int exp = 1; int[] b = new int[N]; 
    int max = input[0]; 
    for(int i = 1; i < N; i++){ 
    if(max <= input[i]) max = input[i]; 
    } 
    while(max/exp > 0){ 
    int[] bucket = new int[10]; 
    for(int i = 0; i < N; i++) bucket[(input[i]/exp) % 10]++; 
    for(int i = 1; i < 10; i++) bucket[i] += bucket[i - 1]; 
    for(int i = N - 1; i >= 0; i--) b[--bucket[(input[i]/exp) % 10]] = input[i]; 
    for(int i = 0; i < N; i++) input[i] = b[i]; 
    exp *= 10; 
    } 
} 

Answer 1

• Третий цикл, чтобы сделать обратное развитие сортировки стабильной.

• Изменение базы до 2 легко: просто изменить количество ведер 2, заменить exp *= 10 с exp *= 2 и (input[i]/exp) % 10 с (input[i]/exp) % 2.

• Для устранения отрицательных чисел вы можете сортировать отрицательные числа отдельно, используя их абсолютное значение в качестве ключа, а затем объединить обратный результат с отсортированными неотрицательными числами.

И, похоже, есть ошибка в вашем фрагменте кода:
должно быть int[] b = new int[N]; вместо int[] b = new int[10];