快速排序(N 个数组应被视为 1，并根据需要重新映射值)

Question

>我有一个数组的链接列表（帖子底部的结构）

每个数组可能具有类似于以下示例的值

Array1[] = {6,36,8,23};
Array2[] = {8,23,5,73};
Array3[] = {2,5,1,9};

我需要对这些进行排序，以便将所有 3 个数组都视为 1 个大数组......

我需要使用快速排序，以便它使用就地处理...我正在使用非常大的阵列，不能使用额外的内存。

结果应该是这样的

Array1[] = {1,2,5,5};
Array2[] = {6,8,8,9};
Array3[] = {23,23,36,73};

目前我只能单独对每个数组进行排序......但这不是我需要的:(

struct iSection {
    unsigned long     Section_Count; // Total # of points in this block of memory
    int              *Section_Arr;   // Point cloud for current block of memory
    struct iSection  *Next;          // Pointer to next section
} iSection;

struct iDatabase {
    struct iSection     *First_Section;
    struct iSection     *Last_Section;
} iDatabase;

Answer 1

这并不难，更多的是一个接口问题，而不是算法问题。

编写一个包装容器，该容器提供用于访问成员和写入的接口（例如operator[] C++），并在内部将size_t index参数映射到正确的数组。这个包装类确实需要每个数组的大小才能正确映射索引。

一个示例伪代码运算符 [] 是：

int& JointDatabase::operator[](size_t index) {
    // database is an iDatabase
    iSection *cur = database.First_Section;
    while (cur != database.Last_Section && index >= cur->Section_Count) {
        index -= cur->Section_Count;
        cur = cur->Next;
    }
    return cur->Section_Arr[index];
}

然后使用此包装器类，就像在快速排序算法中使用普通容器一样。

Answer 2

如果您可以确保在连续内存布局中一个接一个地声明Array1, Array2, and Array3，那么您可以在sort()中给出Array1（第一个），并给出所有数组的组合大小。

要检查连续对齐，您可以使用以下技巧。

template<size_t SIZE1, size_t SIZE2, size_t SIZE3>
bool Check(int (&a1)[SIZE1], int (&a2)[SIZE2], int (&a3)[SIZE3])
{
  return (&a3[SIZE3 - 1] - &a1[0]) == (SIZE1 + SIZE2 + SIZE3);
}

用法

bool aligned = Check(Array1, Array2, Array3);

这是 3 个数组的示例，您可以根据需要制作。您可以传递 Array1,2,3 或 Array3,2,1，具体取决于您的计算机。

Answer 3

只在我的大脑中测试：

struct ArrayWrapper {
    int** arrays;
    int* running_sums;
    ArrayWrapper(int **arrays, int *arrays_length, int N) {
        running_sums = new int*[N+1];
        int sum = 0;
        for (int i = 0; i < N; i++) {
            running_sums[i+1] = sum;
            sum += arrays_length[i];
        }
    }
    int& operator[] (int index) {
        int array_start = binary search `running_sum` for the closest number to `index` (round down)
        return arrays[array_start][index - running_sums[array_start]]
    }
}

因此，如果您有以下内容：

array1 = {...} 
array2 = {...}
...
arrayN = {...}
arrays = {array1, array2, ..., arrayN}
arrays_length = {array1_length, array2_length, ..., arrayN_length}
ArrayWrapper wrapper = new ArrayWrapper(arrays, arrays_length, N);
// wrapper then can be treated like normal array:
wrapper[10] = x;
x = wrapper[10];