如何优化基于距离的坐标向量排序？十万级数据需5秒内完成

你的代码性能拉胯的核心原因是每次循环都对剩余所有点做全排序，再加上vector开头erase的O(n)开销，整体复杂度是O(n² log n)，10万数据量下完全不可能在5秒内跑完。下面给你拆解优化方向，顺便说桶排序的适用性：

一、先改两个最直观的小优化 #

• 去掉sqrt，用平方距离比较
  getDist里的sqrt是没必要的——比较两个距离的大小，平方的大小关系和开根号后完全一致。改成这样能减少大量浮点运算，速度提升很明显：

  // 只计算平方距离，用于比较（用long long避免溢出）
  long long getDistSq(int x1, int y1, int x2, int y2) {
      long long dx = x1 - x2;
      long long dy = y1 - y2;
      return dx*dx + dy*dy;
  }
  // 真要存距离的时候再开根号
  double getDist(int x1, int y1, int x2, int y2) {
      return sqrt((double)getDistSq(x1, y1, x2, y2));
  }
  

• 别再erase vector开头了
  vector的erase(begin())会把后面所有元素往前挪，每次都是O(n)开销，10万次就是O(n²)的浪费。换成用标记数组记录哪些点已被选中，或者把点的索引存在unordered_set里，找到最近邻后直接删除索引即可。

二、核心优化：用空间分区代替全排序找最近邻 #

每次找最近邻不需要给所有剩余点排序，只需要找到当前点的最近点就行。你的初始排序是按x+y分组的思路，刚好可以用来做桶排序式的空间分区，大幅缩小查找范围：

具体做法 #

1. 按s=x+y分桶
   把所有点按s = x + y的值分到不同的桶里，比如用unordered_map<int, vector<int>> buckets（key是s的值，value是该桶内点在原向量中的索引）。如果x和y的最大值不大，直接用vector<vector<int>> buckets(max_s + 1)会更高效。

2. 贪心查找最近邻

   • 从当前点的s值开始，先检查当前s的桶里有没有未被选中的点，计算平方距离找最小的。
   • 如果没有，就依次检查s-1、s+1、s-2、s+2...的桶，直到找到有未选中点的桶，在这些桶里计算距离。
   • 找到最近邻后，标记该点为已选中，从对应的桶里删掉（或用标记数组跳过），然后加入结果路径。

这种方式的好处是：大部分情况下，最近邻的s值和当前点的s值不会差太远，不需要遍历所有点，平均查找时间远低于O(n)。

三、桶排序是不是适用？ #

完全适用！你的初始排序已经是按s=x+y分组的思路，本质就是桶排序的一种。用桶划分点的空间范围，能让你每次找最近邻时只在附近的桶里搜索，不用遍历所有剩余点，这比全排序高效太多。

四、进阶优化：用k-d树做最近邻查找 #

如果数据量真的到10万级别，而且点的分布很散，桶分区的效果可能不够极致，可以用k-d树这种专门用于高维空间最近邻查找的数据结构。构建k-d树的时间是O(n log n)，每次查询最近邻是O(log n)，整体复杂度降到O(n log n)，10万数据量完全能在5秒内跑完。

优化后的代码示例（桶分区版本） #

#include <vector>
#include <unordered_map>
#include <climits>
#include <cmath>
#include <algorithm>

struct Point {
    int ind;
    int x;
    int y;
    double dist;
};

long long getDistSq(int x1, int y1, int x2, int y2) {
    long long dx = x1 - x2;
    long long dy = y1 - y2;
    return dx*dx + dy*dy;
}

double getDist(int x1, int y1, int x2, int y2) {
    return sqrt((double)getDistSq(x1, y1, x2, y2));
}

std::vector<Point> cordSort(std::vector<Point> vect) {
    // 按初始规则排序
    std::sort(vect.begin(), vect.end(), [](const Point &a, const Point &b) {
        if (a.x + a.y != b.x + b.y) {
            return a.x + a.y < b.x + b.y;
        }
        return a.x < b.x;
    });

    // 分桶：key是s=x+y，value是桶内点的索引
    std::unordered_map<int, std::vector<int>> buckets;
    std::vector<bool> visited(vect.size(), false);
    for (int i = 0; i < vect.size(); ++i) {
        int s = vect[i].x + vect[i].y;
        buckets[s].push_back(i);
    }

    std::vector<Point> finalDistVect;
    // 选第一个点作为起点
    int currentIdx = 0;
    visited[currentIdx] = true;
    finalDistVect.push_back(vect[currentIdx]);

    int remaining = vect.size() - 1;
    while (remaining > 0) {
        Point currentPoint = vect[currentIdx];
        int currentS = currentPoint.x + currentPoint.y;
        long long minDistSq = LLONG_MAX;
        int nextIdx = -1;

        // 从currentS开始向外扩展查找桶
        for (int d = 0; ; ++d) {
            // 检查currentS - d的桶
            if (buckets.count(currentS - d)) {
                auto &bucket = buckets[currentS - d];
                for (auto it = bucket.begin(); it != bucket.end(); ) {
                    int idx = *it;
                    if (!visited[idx]) {
                        long long distSq = getDistSq(currentPoint.x, currentPoint.y, vect[idx].x, vect[idx].y);
                        if (distSq < minDistSq) {
                            minDistSq = distSq;
                            nextIdx = idx;
                        }
                    } else {
                        // 移除已访问的点，避免重复遍历
                        it = bucket.erase(it);
                        continue;
                    }
                    ++it;
                }
                // 优化：如果当前最小距离平方 <= d²，更远的桶不可能有更近的点，直接break
                if (nextIdx != -1 && minDistSq <= (long long)d*d) {
                    break;
                }
            }
            // 检查currentS + d的桶（d=0时已检查过，d>0时再处理）
            if (d > 0 && buckets.count(currentS + d)) {
                auto &bucket = buckets[currentS + d];
                for (auto it = bucket.begin(); it != bucket.end(); ) {
                    int idx = *it;
                    if (!visited[idx]) {
                        long long distSq = getDistSq(currentPoint.x, currentPoint.y, vect[idx].x, vect[idx].y);
                        if (distSq < minDistSq) {
                            minDistSq = distSq;
                            nextIdx = idx;
                        }
                    } else {
                        it = bucket.erase(it);
                        continue;
                    }
                    ++it;
                }
                if (nextIdx != -1 && minDistSq <= (long long)d*d) {
                    break;
                }
            }
            // 极端情况：只剩最后一个点，直接选中
            if (remaining == 1 && nextIdx == -1) {
                for (int i = 0; i < vect.size(); ++i) {
                    if (!visited[i]) {
                        nextIdx = i;
                        break;
                    }
                }
                break;
            }
        }

        // 更新结果和状态
        visited[nextIdx] = true;
        finalDistVect.push_back(vect[nextIdx]);
        finalDistVect[finalDistVect.size()-2].dist = getDist(currentPoint.x, currentPoint.y, vect[nextIdx].x, vect[nextIdx].y);
        currentIdx = nextIdx;
        remaining--;
    }

    return finalDistVect;
}

这个桶分区版本的平均时间复杂度接近O(n log n)，远优于原代码的O(n² log n)，10万数据量应该能轻松在5秒内跑完。如果还需要更快，就去实现k-d树的最近邻查找即可。

内容的提问来源于stack exchange，提问作者kabaAli