快速排序（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

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

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

伪代码 operator[] 的示例如下：

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 和 Array3 相继声明并且处于连续的内存布局中，那么您可以在sort() 并给出所有数组的组合大小。

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

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];