快速排序(n个数组应视为1,值根据需要重新映射)

Question

我有一个数组的链接列表(在帖子底部的结构)

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

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

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

我需要使用quicksort,以便它使用就地处理...我正在使用非常大的数组,并且不能使用额外的内存..

结果应该是这样的

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

然后使用此包装类,就像在Quicksort算法中使用普通容器一样.