递归合并排序 - 从原点按升序对坐标进行排序

Question

我有一个作业需要实现合并排序以从原点开始按升序对一些坐标进行排序。我的程序坐标如下（无法编辑；作业需要它）：

// stores the origin (does not change).
struct origin
{
  int x_naught;
  int y_naught;
};

// Individual coordinate to be sorted. 
struct coordinate
{
  int x;
  int y;
};

我有一个未排序的结构坐标数组：struct coordinate **coordArray; 包含 n 个坐标结构指针。

我的问题是，使用合并排序从原点开始按升序对这些坐标进行排序的最有效方法是什么？我最初计划有一个辅助函数，它声明一个单独的数组并将每个坐标的大小（距离公式）存储在 coordArray 数组中，然后将该数组及其长度传递给递归合并排序函数。

我相信这是最简单直接的方法。但是，我不喜欢这个辅助函数需要额外的 n（长度）步骤来对 coordArray 进行排序，甚至在调用 merge_sort 之前。是否有可能以某种方式对这些坐标进行排序将两个结构指针传递给递归 merge_sort 函数？

可能的函数签名：

void merge_sort(struct origin *origin_coord, struct coordinate **coordArray, int length);

我在此处尝试实施的方法中看到的一个问题是如何处理分别对 x 和 y 分量进行排序（即 coordArray[I]->x, coordArray[I]->y) 用于 struct origin 中的 x 和 y（即 origin_coord->x_naught, origin_coord->y_naught).

我理解 O(2n log(n))（或者甚至 O(3nlogn) 将排序后的幅度数组转换回其原始形式：(x, y)）对于 merge_sort 和辅助函数确实没什么大不了的，但如果我要对 10 亿个坐标进行排序，那么额外的 20 亿步工作可能很重要。

Answer 1

如果您不能将距离或其平方存储在 coordinate 结构中，我建议您将原点结构作为参数传递给 mergesort_coords 函数并重新计算两个距离的平方比较功能。与分配和处理辅助结构的开销相比，这种计算非常简单。此外，时间复杂度不变为 O(N.log(N)).

关于x和y排序，您应该指定如何对与原点具有相同距离的坐标进行排序。这个有很多选项，但是比较函数必须是可传递的，并且顺序应该是完整的。

建议原型：

void merge_sort(struct coordinate **coordArray, size_t count,
                int cmp(const struct coordinate *a,
                        const struct coordinate *b,
                        const struct origin *origin_coord),
                struct origin *origin_coord);

int cmpdistance(const struct coordinate *a,
                const struct coordinate *b,
                const struct origin *o)
{
    long long dxa = (long long)a->x - o->x_naught;
    long long dya = (long long)a->y - o->y_naught;
    long long dxb = (long long)b->x - o->x_naught;
    long long dyb = (long long)b->y - o->y_naught;
    long long da = dxa * dxa + dya * dya;
    long long db = dxb * dxb + dyb * dyb;
    if (da < db) return -1;
    if (da > db) return +1;
    // if points are at the same distance, order by x, then by y
    if (a->x < b->x) return -1;
    if (a->x > b->x) return +1;
    if (a->y < b->y) return -1;
    if (a->y > b->y) return +1;
    return 0;
}

递归合并排序 - 从原点按升序对坐标进行排序

Recursive merge sort - sorts coordinates in ascending order from an origin

c

recursion

mergesort

coordinates