Пытаясь понять Bucket сортировочный код

Question

У меня есть три вопроса о следующем коде:

static void funct(int[] list) { 
    final int N = 20; 

    java.util.ArrayList[] buckets = new java.util.ArrayList[N]; 
    for(int i = 0; i< list.length; i++) { 
    int key = list[i]; 
    if(buckets[key] = null) 
      buckets[key].add(list[i]); 
    } 
    int k = 0 
    for(int i = 0; i <buckets.length; i++) { 
     if(buckets[i] != null) { 
      for(int j = 0; j< buckets[i].size(); j++) 
       list[k++] = (Integer)buckets[i].get(j); 
     } 
    } 

}

1. алгоритм имеет существенный недостаток, является то, что он будет работать только до 20 элементов и что он имеет плохую сложность?

2. Точка кода предназначена для сортировки списка элементов - они помещаются в массив, а затем помещаются в ведра, после чего их снова помещают из ведер в массив.

3. Это то, на что я нахожусь в тупике, как бы вы изменили метод, чтобы передать массив, содержащий объекты другого класса вместо целых чисел?

Answer 1

Адресация ваши вопросы:

1. Это два недостатка. Не обращайте внимания на сложность на мгновение; рассмотрите, как он должен работать более чем для 20 элементов. Для сортировки ковша идея состоит в том, что вы выбираете ковш на основе положения элемента в общем диапазоне элементов. Самый простой способ сделать это на компьютере с двоичными целыми числами - это выбрать первые несколько бит (наиболее значимых бит) в числе и использовать число из двух кодов, например 16 или 32. Вы можете получить наиболее значимые бит (и, следовательно, вычислить ведро) с помощью операции и (&). Затем вы можете использовать биты для непосредственного выбора ведра.

2. Идея сортировки ковша состоит в том, чтобы использовать элемент сортировки радикса для начального прохода над входом, а затем использовать разные сортировки (или отсортированную сортировку радикса) на небольших ведрах, которые могут быть небольшими и более легко сортировать или конкатенация всех ведер (например, обратно в массив), могут быть отсортированы с меньшей сложностью.

3. Сортировка ковша основана на знании полного диапазона ввода, так что вы можете разделить этот диапазон на сегменты и затем классифицировать вход по отдельности. Самый простой способ сделать это - ввести число. Если порядок на входе является только относительным, и нет известных абсолютов и нет простого способа выяснить, где в общем диапазоне какой-либо один элемент, то сортировка ковша не подходит.

Answer 2

Это хороший вопрос о домашнем задании. Многие из вопросов являются субъективными и почти наверняка зависят от вашей работы.

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

Кроме того, если кто-либо, находящийся за пределами классной комнаты, увидел это, ответ должен был бы просто использовать встроенную сортировку массивов и выбросить этот мусор!