c# - 基于另一个一维数组的 3 维数组快速排序

Question

我有一个包含值的 3D 数组，我想根据 1D 数组中列出的值对其进行排序。 例如，

3d 数组的值为:

1 2 3
4 5 6
7 8 9

一维数组的值为:

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。