Расширенная сортировка / перестановка массивов в Java

Question

Итак, у меня есть массив со следующими теоретическими значениями:

int[] elements = {A1, A2, B1, B2,
                  A3, A4, B3, B4,
                  C1, C2, D1, D2,
                  C3, C4, D3, D4};

Иллюстративный рисунок:

                  + - + - + - + - +
                  | A | A | B | B |
                  + - + - + - + - +
                  | A | A | B | B |
                  + - + - + - + - +
                  | C | C | D | D |
                  + - + - + - + - +
                  | C | C | D | D |
                  + - + - + - + - +

Проще говоря, я бы хотел, чтобы массив был переставлен следующим образомформа:

int[] elements = {A1, A2, A3, A4,
                  B1, B2, B3, B4,
                  C1, C2, C3, C4,
                  D1, D2, D3, D4};

Иллюстративный рисунок:

                  + - + - + - + - +
                  | A | A | A | A |
                  + - + - + - + - +
                  | B | B | B | B |
                  + - + - + - + - +
                  | C | C | C | C |
                  + - + - + - + - +
                  | D | D | D | D |
                  + - + - + - + - +

Этот конкретный пример содержит четыре сектора (A, B, C и D), но нужный мне алгоритм должен работать сколько угодно или малосекторов, которые содержит массив, и сколько элементов содержит каждый сектор.

Размер каждого сектора известен (ширина сектора и высота сектора), а также количество секторов (строки и столбцы). Все сектора имеют одинаковый размер (ширину и высоту). Количество секторов должно быть описано как два значения (строки и столбцы), которые затем умножаются, чтобы составить фактическую сумму секторов.Например.если требуется 5 секторов, то можно указать 1 строку и 5 столбцов.

Ниже приведен пример того, как может выглядеть метод, формирующий этот вид:

public int[] sectorSort(int[] elements,
                        int sectorWidth,
                        int sectorHeight,
                        int columns,
                        int rows);

Пример другого сектораsetups:

                  Columns: 5
                  + - + - + - + - + - + - + - + - + - + - +
                  | A | A | B | B | C | C | D | D | E | E |
     Rows: 1      + - + - + - + - + - + - + - + - + - + - +
                  | A | A | B | B | C | C | D | D | E | E |
                  + - + - + - + - + - + - + - + - + - + - +

                  Columns: 2
                  + - + - + - + - +
                  | A | A | B | B |
                  + - + - + - + - +
                  | A | A | B | B |
                  + - + - + - + - +
                  | C | C | D | D |
     Rows: 3      + - + - + - + - +
                  | C | C | D | D |
                  + - + - + - + - +
                  | E | E | F | F |
                  + - + - + - + - +
                  | E | E | F | F |
                  + - + - + - + - +

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

Спасибо!

РЕДАКТИРОВАТЬ1: Ясность.

РЕДАКТИРОВАТЬ2:Добавлено больше условий и уточнений.

Answer 1

Вы не получите лучшую временную сложность, чем эта: Он создает новый массив и копирует в него каждый сектор.

static T[] sectorSort<T>(T[] elements, int sectorWidth, int sectorHeight, int columns, int rows)
        {
            T[] sortedElements = new T[elements.Length];
            int n = 0;
            int arrWidth = sectorWidth * columns;
            for(int secY = 0; secY < rows; secY++)
                for (int secX = 0; secX < columns; secX++)
                {
                    int baseIndex = secY * arrWidth * sectorHeight + secX * sectorWidth;
                    for(int y = 0; y < sectorHeight; y++)
                        for (int x = 0; x < sectorWidth; x++)
                        {
                            int sourceIndex = baseIndex + y * arrWidth + x;
                            sortedElements[n++] = elements[sourceIndex];
                        }
                }
            return sortedElements;
        }

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

РЕДАКТИРОВАТЬ: Фиксированный код

EDIT2: тестовая настройка (C #)

    int[] array = new int[]
    {
        11, 12, 13, 21, 22, 23, 51, 52, 53,
        14, 15, 16, 24, 25, 26, 54, 55, 56,
        17, 18, 19, 27, 28, 29, 57, 58, 59,
        31, 32, 33, 41, 42, 43, 61, 62, 63,
        34, 35, 36, 44, 45, 46, 64, 65, 66,
        37, 38, 39, 47, 48, 49, 67, 68, 69,
        71, 72, 73, 81, 82, 83, 91, 92, 93,
        74, 75, 76, 84, 85, 86, 94, 95, 96,
        77, 78, 79, 87, 88, 89, 97, 98, 99,
    };
    int[] sorted = sectorSort(array, 3, 3, 3, 3);
    for (int y = 0; y < 9; y++)
    {
        for (int x = 0; x < 9; x++)
            Console.Write(sorted[x + y * 9] + " | ");
        Console.WriteLine("\n");
    }

Answer 2

Вы могли бы взять прямой алгоритм, повторяющий все сектора и все элементы в них, чтобы переставить их. Это будет O (n * m), n = количество секторов и m = количество элементов на сектор. Но вам придется переставить весь массив. В качестве альтернативы (если память критична) вы можете создать секторное представление исходного массива, для создания которого потребуется O (n), а затем O (m) для чтения значений одного сектора.

Таким образом, чтение всех секторов потребует O (n * m) в обоих случаях. Какое улучшение вы ожидаете?