Можете ли вы хранить несколько целых чисел в одном индексе массива?

Question

Я пытаюсь выполнить радикальную сортировку, и некоторые алгоритмы, которые я видел, имеют массив buckets[ ], который должен содержать несколько целых чисел в одном индексе массива bucket, вот алгоритм, на который я ссылаюсь:

Действительно ли возможно иметь несколько целых чисел в одном индексе? А как так?
Или есть более простой алгоритм сортировки по основанию?

Спасибо!!

Answer 1

Ничего себе, массивы и списки не способ реализовать основную сортировку. Да, списки работают, но это замедляет их, когда я это делал, это было медленнее, чем сортировка слиянием. Лучший способ состоит в том, чтобы реализовать частотный массив как часть счетной сортировки для каждого байта. Я разместил свой код здесь, только в отношении параллельной сортировки. Надеюсь, поможет.

Answer 2

Два случая создают ведра

• цифры не уникальны
• Сортировка по основанию сортирует по каждой позиции цифры (десятки, десятки, сотни) перед переходом к следующей - так что 003 и 019, если сортировка по первой цифре будет совпадать.

Первый случай действительно является вырожденным вторым.

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

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

Answer 3

В дополнение к возможности представления сегмента в виде списка или массива, можно использовать фрагмент массива. В этом случае целевой массив имеет тот же общий размер, что и входной массив. Например, у вас есть 2 элемента в корзине 0, 2 в корзине 1, 3 в корзине 2, 1 в корзине 3 и 2 в корзине 5.

Bucket 0 : d[0], d[1]
Bucket 1 : d[2], d[3]
Bucket 2 : d[4], d[5], d[6]
Bucket 3 : d[7]
Bucket 5 : d[8], d[9]

Делая это таким образом, сортировка должна отслеживать следующий индекс для каждого сегмента.

Answer 4

Да, можно добавить несколько int в массив, но вам нужно иметь массив, где каждый элемент является Object а не int,

Например...

// the items to store in the array, which contain 3 ints
public class Bucket {
    int number1 = -1;
    int number2 = -1;
    int number3 = -1;

    public void addInt(int number){
        if (number1 == -1){
            number1 = number;
        }
        else if (number2 == -1){
            number2 = number;
        }
        else if (number3 == -1){
            number3 = number;
        }
    }
}

// the array, as used in other classes
Bucket[] bArray = new Bucket[6]; // 6 items in the array, where each item is a Bucket that contains 3 ints

// assigning ints into the array
bArray[2].addInt(56); // add the int '56' to the bucket at index '2' of the array

// You could also use other Array-like structures
ArrayList<Bucket> bList = new ArrayList<Bucket>();

Конечно, если у вас не всегда <=3 элементов в корзине, вы можете просто изменить класс Bucket на использование массива или List как его переменная, а не отдельная ints.

Вы также можете использовать многомерные массивы...

// creating the buckets
int[][] buckets = new int[6][3];

// assigning ints into the array
bArray[2][0] = 56; // add the int '56' to the bucket at index '2' of the array, position '0'

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

1. Предметы в корзине не пусты, когда вы пытаетесь получить к ним доступ
2. Когда вы добавляете число в корзину, вам нужно определить следующую позицию во втором измерении, которая является пустой, чтобы не перезаписывать intс, которые уже там.

Если по этим причинам я бы рекомендовал использовать массив на основе объектов поверх многомерного массива.

Answer 5

bucket будет int[] (или же List или что-нибудь, что может хранить несколько предметов) сам.

Вы не можете поместить больше одной вещи в 1 индекс.

int[] array = new array[6];
int value = array[5];

больше не будет работать, если было более одного int.

Самый простой, вероятно, использовать int[][] массив. Теперь каждый индекс в левом поле относится к целому массиву. Эти массивы тоже могут быть разной длины:

Java Jagged Array