请教一个问题更优的算法

这是题目的内容：我个人是这样想的：先将要输入的所有坐标存到一个结构数组（结构含有序号，横坐标，纵坐标）中，然后再遍历所有结构数组，对每个结构按x，y的情况用选择排序法进行排序，最后再遍历所有结构数组依次输出其中的序号。但觉得这样做既耗时间有耗内存，请问各位大神能没有更好的思路或解法，麻烦指点一下，谢谢
10分	使用qsort()： #include <search.h> typedef struct point { int s; int x; int y; }Point; Point ps; int i, n; int cmp(Point p1, Point p2) { if (p1->x < p2->x) return 0; else if (p1->x > p2->x) return 1; else return p1->y > p2->y; } int main() { scanf("%d", &n); ps = malloc(sizeof(Point)n); i = 0; //读入坐标 while (i < n) { scanf("%d%d%d", &ps[i].s, &ps[i].x, &ps[i].y); i++; } qsort(ps, n, sizeof(Point), cmp); for (i = 0; i < n; i++) printf("%d ", ps[i].s); printf("\n"); free(ps); return 0; }
5分	我的思路是用内存换时间其实X坐标的个数最多也就20W，那就弄个大小是20W的数组，每个数组的索引是X，每个数组的元素是一个链表，链表按照Y来排序当然，这种算法如果遇到所有X相同，只有Y不同的时候，那效率就灰常低了空间时间折中的排序算法是桶排序，原理类似，但是内存用的少一些，楼主可以搜索一下，看看会不会有启发
5分	感觉这个数据是＜10W的用快排可能好点把？
	引用 2 楼 hnwyllmm 的回复: 我的思路是用内存换时间其实X坐标的个数最多也就20W，那就弄个大小是20W的数组，每个数组的索引是X，每个数组的元素是一个链表，链表按照Y来排序当然，这种算法如果遇到所有X相同，只有Y不同的时候，那效率就灰常低了空间时间折中的排序算法是桶排序，原理类似，但是内存用的少一些，楼主可以搜索一下，看看会不会有启发好的，我试试
	引用 2 楼 hnwyllmm 的回复: 我的思路是用内存换时间其实X坐标的个数最多也就20W，那就弄个大小是20W的数组，每个数组的索引是X，每个数组的元素是一个链表，链表按照Y来排序当然，这种算法如果遇到所有X相同，只有Y不同的时候，那效率就灰常低了空间时间折中的排序算法是桶排序，原理类似，但是内存用的少一些，楼主可以搜索一下，看看会不会有启发引用 2 楼 hnwyllmm 的回复: 我的思路是用内存换时间其实X坐标的个数最多也就20W，那就弄个大小是20W的数组，每个数组的索引是X，每个数组的元素是一个链表，链表按照Y来排序当然，这种算法如果遇到所有X相同，只有Y不同的时候，那效率就灰常低了空间时间折中的排序算法是桶排序，原理类似，但是内存用的少一些，楼主可以搜索一下，看看会不会有启发你好，这是我自己写的代码，但提交后是Time Limit Exceeded ，麻烦指点一下其中可以优化的地方，谢谢 #include<stdio.h> #include<stdlib.h> struct zuobiao { int xuhao; int x; int y; }; int main() { int n,i,t; struct zuobiao p; scanf(“%d”,&n); p=(struct zuobiao)malloc((n+1)*sizeof(struct zuobiao)); for(i=1;i<=n;i++) { scanf(“%d%d%d”,&(p+i)->xuhao,&(p+i)->x,&(p+i)->y); } for(i=1;i<n;i++) for(t=i+1;t<=n;t++) { if(((p+i)->x)>((p+t)->x)\|\|((p+i)->x)==((p+t)->x)&&((p+i)->y)>((p+t)->y)) { p[0]=p[i]; p[i]=p[t]; p[t]=p[0]; } } for(i=1;i<=n;i++) printf(“%d “,(p+i)->xuhao); printf(“\n”); return 0; }
5分	关于排序，还是数据结构里面的几种算法比较成熟，这里可以使用哈希排序算法，n lg(n)，的时间复杂度，用两个嵌套就行了
5分	楼主你用的是冒泡排序吧，这个有什么说的，肯定超时，最慢的算法
5分	＜1000个元素，冒泡排序＜100000个元素，qsort函数＜10000000个元素，放数据库中，建索引，（B+树排序） ≥10000000个元素，没用到过。
5分	两种方案：１：先输入所有数据，然后用快排排序，快排平均时间复杂度是O(nlogn),但最坏情况时间复杂度为O(n^2)，不过快排函数Ｃ语言的标准库已经帮你实现了：qsort,直接用就可以了。２：用红黑树保存数据，在输入数据的时候就直接进行了排序，红黑树插入操作最坏情况时间复杂度为O(log(n))，所以输入+排序总的时间复杂度为O(nlogn)，但红黑树你要自己实现。
	引用 1 楼 zhangxiangDavaid 的回复: 使用qsort()： #include <search.h> typedef struct point { int s; int x; int y; }Point; Point ps; int i, n; int cmp(Point p1, Point p2) { if (p1->x < p2->x) return 0; else if (p1->x > p2->x) return 1; else return p1->y > p2->y; } int main() { scanf("%d", &n); ps = malloc(sizeof(Point)n); i = 0; //读入坐标 while (i < n) { scanf("%d%d%d", &ps[i].s, &ps[i].x, &ps[i].y); i++; } qsort(ps, n, sizeof(Point), cmp); for (i = 0; i < n; i++) printf("%d ", ps[i].s); printf("\n"); free(ps); return 0; } 引用 1 楼 zhangxiangDavaid 的回复: 使用qsort()： #include <search.h> typedef struct point { int s; int x; int y; }Point; Point ps; int i, n; int cmp(Point p1, Point p2) { if (p1->x < p2->x) return 0; else if (p1->x > p2->x) return 1; else return p1->y > p2->y; } int main() { scanf("%d", &n); ps = malloc(sizeof(Point)n); i = 0; //读入坐标 while (i < n) { scanf("%d%d%d", &ps[i].s, &ps[i].x, &ps[i].y); i++; } qsort(ps, n, sizeof(Point), cmp); for (i = 0; i < n; i++) printf("%d ", ps[i].s); printf("\n"); free(ps); return 0; } 谢谢指点
	谢谢各位的指点，学到了不少新知识

文章评论已关闭！