Быстрая сортировка трехмерного массива на основе другого одномерного массива

Question

У меня есть 3D-массив, содержащий значения, и я хочу отсортировать его по значениям, перечисленным в 1D-массиве. Например,

Массив 3d имеет значения:

1 2 3
4 5 6
7 8 9

и массив 1D имеет значения:

20 
11
12

так что если мы посчитали, что 3D-массив связан с 1D-массивом (строки связаны друг с другом), то результат, который я хочу получить в 3D-массиве:

4 5 6 
7 8 9
1 2 3

Я искал алгоритм быстрой сортировки, но не смог найти то, что хотел.

Answer 1

Вы можете реализовать «быструю сортировку аргументов», которая возвращает индексы, которые довольно легко сортируют массив.Вот реализация на C ++:

#include <algorithm>

template <class IndexContainer, class DataContainer>
void arg_qsort(IndexContainer& indices,
               const DataContainer& data,
               int left,
               int right)
{
  int i = left;
  int j = right;
  int pivot = left + (right - left) / 2;

  while (i <= j)
  {
    while (data[indices[i]] < data[indices[pivot]])
      ++i;
    while (data[indices[j]] > data[indices[pivot]])
      --j;
    if (i <= j)
    {
      std::swap(indices[i], indices[j]);
      ++i;
      --j;
    }
  }

  if (left < j)
    arg_qsort(indices, data, left, j);
  if (i < right)
    arg_qsort(indices, data, i, right);
}


///
/// Compute the indices that would sort the given data.
///
template <class IndexContainer, class DataContainer>
void argsort(IndexContainer& indices, const DataContainer& data)
{
  int size = indices.size();
  if (size == 0)
    return;
  for (int i = 0; i < size; ++i)
  {
    indices[i] = i;
  }
  arg_qsort(indices, data, 0, size - 1);
}

Теперь вы можете вычислить порядок строк в вашем двумерном массиве, используя argsort.Для вашего примера argsort вернет 1 2 0.

Answer 2

Если вы намереваетесь использовать C #, вы можете пойти на запрос LINQ с предложением «group row by expression ».В зависимости от исходных данных и контекста это может быть даже предпочтительным способом сортировки данных.