Ниже приведен код для целочисленного Radix Sort, который использует измененную сортировку Bucket для сортировки массива. В сортировке ведра используется массив списков, где количество списков совпадает с базовым (8-восьмеричное, 10-значное, 16-шестнадцатеричное).Создание настраиваемого списка для Radix Sort
Цифра «i», полученная с помощью операции radix, вводится в список «i» массива списка. На самом деле это не цифра, а индекс в массиве ввода, который помещается в список. Для этого требуется сканирование входного массива, следовательно, время будет равно O (n). После этого индексы получают список по списку, то есть все индексы в предыдущем списке сначала обрабатываются, прежде чем переходить к следующему списку, это массив списка, а затем временный результат помещается в temp_array.
Наконец, замена указателей массивов позволяет избежать необходимости скопировать temp_array на input_array. Когда уменьшается радиус, массив списков повторно инициализируется в новых ячейках памяти. Этот способ позволяет избежать необходимости метода list.remove (index), временная сложность которого равна O (n) из-за смещения элементов. Будут ли удалены старые ячейки памяти с помощью JVM во время выполнения или они, в конце концов, приведут к переполнению памяти?
Удаление из списка по индексу 0 и последнему индексу (= N), (list.remove (0), list.remove (N)) Какой из этих подходов быстрее?
Это хорошая идея (будет работать быстрее), чтобы создать индивидуальный список (для хранения ведер) с помощью двух методов удаления (remove1(), remove2()), где один из них удаляет элемент с самого начала (требуется для возрастания) списка в O (1) времени, а другое в конце (требуется для нисходящего порядка) в то же время O (1) (без необходимости смещения элементов, а также поддержки произвольного доступа arrayList)? (Я думаю, что не может быть и того и другого.)
Если да, то каковы были бы необходимые строки кода и импортированные классы?
В случае отсутствия какого-либо другого метода для улучшения скорости алгоритма?
Меняет ли основание базу, изменяя производительность, т. Е. Зависит от производительности на базе? В случае «да», какова оптимальная база?
Любые идеи о том, как преобразовать его в многопоточную версию? Я думаю, что это невозможно.
import java.util.List ;
import java.util.ArrayList ;
public class Radix_Sort
{
// input_array[] -> the array to be sorted
// temp_array[] -> the array to hold the temporary result, must be equal to or larger than input_array in size
// radix -> is the number of digits in maxiumum value in array : floor of log(MaxValue)
// length -> length of input_array[]
// base -> Base of the number system used
public static int[] ASC(int input_array[], int temp_array[], int radix, int length, int base)
{
int div = 1 ;
int swap[] ;
int i, s_indx, Y, j ;
while(radix > 0)
{
List<List<Integer>> buckets = new ArrayList<List<Integer>>(base) ;
i = 0 ;
while(i < base)
{
buckets.add(new ArrayList<Integer>()) ;
i++ ;
}
i = 0 ;
while(i < length)
{
buckets.get((input_array[i]/div) % base).add(i) ;
i++ ;
}
s_indx = 0 ;
i = 0 ;
while(i < base)
{
Y = buckets.get(i).size() ;
j = 0 ;
while(j < Y)
{
temp_array[s_indx++] = input_array[buckets.get(i).get(j)] ;
j++ ;
}
i++ ;
}
swap = input_array ;
input_array = temp_array ;
temp_array = swap ;
div = div * base ;
radix--;
}
return input_array ;
}
public static int[] DSC(int input_array[], int temp_array[], int radix, int length, int base)
{
int div = 1 ;
int swap[] ;
int i, s_indx, Y ;
while(radix > 0)
{
List<List<Integer>> buckets = new ArrayList<List<Integer>>(base) ;
i = 0 ;
while(i < base)
{
buckets.add(new ArrayList<Integer>()) ;
i++ ;
}
i = 0 ;
while(i < length)
{
buckets.get((input_array[i]/div) % base).add(i) ;
i++ ;
}
s_indx = length - 1 ;
i = 0 ;
while(i < base)
{
Y = buckets.get(i).size() ;
while(Y > 0)
{
Y-- ;
temp_array[s_indx--] = input_array[buckets.get(i).get(Y)] ;
}
i++ ;
}
swap = input_array ;
input_array = temp_array ;
temp_array = swap ;
div = div * base ;
radix--;
}
return input_array ;
}
}// end of class
Добавьте ярлык ** 'java' **, чтобы увеличить количество зрителей !!! –
@ J.Piquard, спасибо большое – ytoamn