Реализация Pigeonhole Сортировать по Java

Question

Что такое простейшая реализация Pigeonhole Сортировка в Java? Массив массивов-списков идеален, но Java делает это трудным, если вы хотите оставаться безопасным по типу. Можно использовать массив массивов или массив-список списков массивов, но они несколько неудобны. Мне было интересно, была ли общая рекомендация относительно того, какая структура данных лучше.

Answer 1

Прежде всего, если вы хотите достичь теоретической вычислительной сложности сортировки свиноматок, вы должны использовать LinkedList<T>, а не ArrayList<T>. Многие люди забывают, что амортизированная стоимость вставки в ArrayList<T> составляет O (log n) с n количество элементов в списке.

Как вы заметили, существует проблема с созданием массива общего (-зависимого) типа. Но вы можете обойти это, используя this answer.

Так сказать n этому количество ключей и f является функцией вычисления ключевых (карт на целое число между 0 и n-1 (включительно)), на котором мы хотим разобраться, то (сортировка рядного) алгоритма в Java 8 (с функциональным программированием) выглядит следующим образом:

public static<T> void pigeonholeSort (T[] tosort, Function<T,Integer> f, int n) { 
    LinkedList<T>[] holes = (LinkedList<T>[]) new LinkedList[n]; 
    for(int i = 0; i < n; i++) { 
     holes[i] = new LinkedList<T>(); 
    } 
    for(T t : tosort) { 
     holes[f.apply(t)].add(t); 
    } 
    for(int i = 0, j = 0; i < n; i++) { 
     for(T t : holes[i]) { 
      tosort[j++] = t; 
     } 
    } 
} 

Вы можете запустить этот код, например, с:

String[] toSort = new String[] {"Foo","Bar","Baz","Fubar","Qux"}; 
pigeonholeSort(toSort,x -> (Integer) (x.charAt(0)-'A'),26); 
System.out.println(Arrays.toString(toSort)); 

(при условии, что вы используете только строки, начинающиеся с буквы в верхнем регистре).