c++ - 坐标排序

Question

假设我有n个点

(x,y1),(x2,y2),.....(xn,yn)

我的目标是以这样一种方式连接这些点，得到一条没有自交点的样条曲线。我的方法是通过增加 x 值的顺序来对这些元素进行排序，如果它们相等，则比较 y 值。这是我的方法:

#include<iostream>
#include<ctime>

using namespace std;
#define N  1000
struct  Point
{
    int x;
    int y;

}point[N];
int main()
{
    int start=clock();
    int n;
    cout<<" enter  number of coordinantes " <<endl;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>point[i].x>>point[i].y;

    for(int i=1;i<=n-1;i++){
        for(int j=i+1;j<=n;j++)
        {
            if(point[i].x>point[j].x)
            {
                int t=point[i].x;
                point[i].x=point[j].x;
                point[j].x=t;

            }
            if( point[i].x==point[j].x)
            {

                if(point[i].y>point[j].y)
                {
                    int s=point[i].y;
                    point[i].y=point[j].y;
                    point[j].y=s;
                }
                }


            }

    }
    int end=clock();
    cout<<"coordinantes are :"<<endl;
    for(int i=1;i<=n;i++)
        cout<<point[i].x<<" "<<point[i].y<<endl;
    cout<<(end-start)/(float)CLOCKS_PER_SEC<<endl;
    return 0;
}

当我输入数量等于 20 的元素时，它花费了 102.59 毫秒(配备 2.5 RAM、1.87 GH 的笔记本电脑)。我的方法是最优的还是存在更好的方法？

Answer 1

算法中的瓶颈是排序 - 即O(n^2)。它可以在 O(nlogn) 中完成——这在渐进上要好得多。

您应该首先使用更快的排序对数据进行排序，然后迭代您的元素以调用算法的第二阶段。

另请注意，从设计上讲 - 通常 将程序的各个部分分开是一种很好的做法 - 在您的情况下 - 将排序和后面分开遍历。

对于排序，你可能想看看 std::sort()你可能想熟悉 quicksort