1

我有两个 int 数组 *start 和 *end，它们的大小可能是 500 万。*start 存储边的起始节点编号，*end 存储结束节点编号。现在我想以升序方式对 *start 进行排序并存储新的排序方案，就像在排序之前一样：

start[0] = 5
start[1] = 7
start[2] = 8
start[3] = 1
start[4] = 4

排序后变成

start[0] = 1
start[1] = 4
start[2] = 5
start[3] = 7
start[4] = 8

我还想存储新的订购方案“3 4 0 1 2”。我想存储这个新的排序方案的原因是我需要在重新排列 *end 时使用它。C 库中有一个函数 qsort() 但它只能完成排序工作但不存储排序方案。有没有其他功能可以两者兼得？或者如何自己编写一个函数？非常感谢。

4

2 回答 2

2

qsort()只要start比较函数可以访问您的数组，您就可以使用标准函数执行此操作。您这样做的方式是为新的排序顺序创建数组并根据数组的值对其进行排序start。比较函数如下所示：

int compare(const void *a, const void *b)
{
    int start_a = start[*(const size_t *)a];
    int start_b = start[*(const size_t *)b];

    return (start_a > start_b) - (start_a < start_b);
}

然后生成排序顺序是：

size_t i;
size_t *sortorder = malloc(n * sizeof sortorder[0]);

for (i = 0; i < n; i++)
    sortorder[i] = i;

qsort(sortorder, n, sizeof sortorder[0], compare);

（其中和数组n中的元素数）。这将留下包含问题中示例数据的值，您可以使用它来创建新数组和数组。startendsortorder{ 3, 4, 0, 1, 2 }startend

于 2013-04-09T04:11:37.037 回答
1

您可能应该查看您正在使用的数据结构。如果您使用：

struct data
{
    int start;
    int end;
};

然后，您可以分配此结构的单个数组，并使用标准qsort()函数一次对其进行排序（一次）。您不需要排序顺序数组来对数组进行排序，end因为起始值和结束值是并行移动的，因为它们是相同结构的成员：

int data_cmp(const void *vp1, const void *vp2)
{ 
    const struct data *dp1 = vp1;
    const struct data *dp2 = vp2;
    if (dp1->start < dp2->start)
        return -1;
    else if (dp1->start > dp2->start)
        return +1;
    else
        return 0;
}

然后，在其他一些功能中：

size_t nitems = 5000000;
struct data *array = malloc(nitems * sizeof(*array));

// ...load the array with start and end point values...

qsort(array, sizeof(array[0]), nitems, data_cmp);
于 2013-04-09T04:29:44.137 回答