关于qsort()运用问题的深思？
我是一名ACMer,菜鸟而已，前几天刚学了最近点对问题，并在杭电上找到相应题目做。结果本来以为简单的题目，一直WA或
TL，问了很多人也看了很多AC的code, 发现我的思路是完全正确的，但不知道为什么不能AC，唯一不同的就是我是用qsort()排序
，别人是sort()；我以前都是用qsort()函数都米错，这应该不会错吧，到最最最最最后绝望的时候就改成了sort()居然AC了，
无限的囧啊，以前都是这么写过来的为什么这次就不行了。纠结！问了很多人依旧不知道问题在于哪里，希望知道的前辈能指
点我一二。在此，非常谢谢！
先贴题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1007
在贴我的4个代码（qsort()中cmp函数有所不同）：
第一个AC代码，sort()函数排序：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
struct node
{
double x, y;
int index;
}px[100002], py[100002];
bool cmpx(const node &a, const node &b)
{
return a.x < b.x;
}
bool cmpy(const node &a, const node &b)
{
return a.y < b.y;
}
double Get_Distance(struct node a, struct node b)
{
return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}
double Closest(int left, int right, struct node py[])
{
double dmin = 99999999;
int i, j, k;
//there are less than three points,then rude
if(right - left < 3)
{
for(i = left; i < right; i++)
for(j = i+1; j <= right; j++)
{
double temp;
temp = Get_Distance(px[i], px[j]);
if(dmin > temp)
dmin = temp;
}
return dmin;
}
int mid = (right+left)/2;
node *pyl = new node[mid - left + 1];
node *pyr = new node[right - mid];
//divide to two part
j = k = 0;
for(i = 0; i <= right-left; i++)
if(py[i].index <= mid)
pyl[j++] = py[i];
else
pyr[k++] = py[i];
double left_min = Closest(left, mid, pyl);
double right_min = Closest(mid+1, right, pyr);
if(dmin > left_min)
dmin = left_min;
if(dmin > right_min)
dmin = right_min;
//middle points part
k = 0;
for(i = 0; i <= right-left; i++)
if(fabs(py[i].x - px[mid].x) < dmin)
py[k++] = py[i];
for(i = 0; i < k-1; i++)
for(j = i+1; j < k && j < i+7; j++)
{
double temp;
temp = Get_Distance(py[i], py[j]);
if(dmin > temp)
dmin = temp;
}
delete [] pyl;
delete [] pyr;
return dmin;
}
int main()
{
int N, i;
while(scanf("%d", &N) != EOF)
{
if(!N)
break;
for(i = 0; i < N; i++)
scanf("%lf%lf", &px[i].x, &px[i].y);
//qsort x and mark position
sort(px, px+N, cmpx);
for(i = 0; i < N; i++)
px[i].index = i;
//copy px[]->py[] and qsort y
memcpy(py, px, sizeof(px));
sort(py, py+N, cmpx);
printf("%.2lf\n", Closest(0, N-1, py)/2.0);
}
return 0;
}
////////////////////////////////////////////////////////
第二个qsort()排序，TL（超时）代码 ，注意看qsort()中的cmp函数
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
struct node
{
double x, y;
int index;
}px[100002], py[100002];
int CmpX(const void *a, const void *b)
{
return ((struct node *)a)->x > ((struct node *)b)->x ? 1 : -1;
}
int CmpY(const void *a, const void *b)
{
return ((struct node *)a)->y > ((struct node *)b)->y ? 1 : -1;
}
double Get_Distance(struct node a, struct node b)
{
return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}
double Closest(int left, int right, struct node py[])
{
double dmin = 99999999;
int i, j, k;
//there are less than three points,then rude
if(right - left < 3)
{
for(i = left; i < right; i++)
for(j = i+1; j <= right; j++)
{
double temp;
temp = Get_Distance(px[i], px[j]);
if(dmin > temp)
dmin = temp;
}
return dmin;
}
int mid = (right+left)/2;
node *pyl = new node[mid - left + 1];
node *pyr = new node[right - mid];
//divide to two part
j = k = 0;
for(i = 0; i <= right-left; i++)
if(py[i].index <= mid)
pyl[j++] = py[i];
else
pyr[k++] = py[i];
double left_min = Closest(left, mid, pyl);
double right_min = Closest(mid+1, right, pyr);
if(dmin > left_min)
dmin = left_min;
if(dmin > right_min)
dmin = right_min;
//middle points part
k = 0;
for(i = 0; i <= right-left; i++)
if(fabs(py[i].x - px[mid].x) < dmin)
py[k++] = py[i];
for(i = 0; i < k-1; i++)
for(j = i+1; j < k && j < i+7; j++)
{
double temp;
temp = Get_Distance(py[i], py[j]);
if(dmin > temp)
dmin = temp;
}
delete [] pyl;
delete [] pyr;
return dmin;
}
int main()
{
int N, i;
while(scanf("%d", &N) != EOF)
{
if(!N)
break;
for(i = 0; i < N; i++)
scanf("%lf%lf", &px[i].x, &px[i].y);
//qsort x and mark position
qsort(px, N, sizeof(px[0]), CmpX);
for(i = 0; i < N; i++)
px[i].index = i;
//copy px[]->py[] and qsort y
memcpy(py, px, sizeof(px));
qsort(py, N, sizeof(py[0]), CmpY);
printf("%.2lf\n", Closest(0, N-1, py)/2.0);
}
return 0;
}
第三个，qsort()，WA（错误）代码：（其他地方一样的，就是qsort()中cmp函数不同）
int CmpX(const void *a, const void *b)
{
return ((struct node *)a)->x > ((struct node *)b)->x;
}
int CmpY(const void *a, const void *b)
{
return ((struct node *)a)->y > ((struct node *)b)->y;
}
第四个，qsort()，AC（成功）代码：（其他地方一样，就是cmp函数不同）
int CmpX(const void *a, const void *b)
{
if( ((struct node *)a)->x < ((struct node *)b)->x )
return -1;
else
if( ((struct node *)a)->x == ((struct node *)b)->x )
return 0;
else
return 1;
}
int CmpY(const void *a, const void *b)
{
if( ((struct node *)a)->y < ((struct node *)b)->y )
return -1;
else
if( ((struct node *)a)->y == ((struct node *)b)->y )
return 0;
else
return 1;
}
///////////////////////////////////////////////////////////////////////////
我以前都是第2个 或 第3个这么写的cmp函数排序都可以，但是这次 必须要把cmp的三种情况都写全，
才能够AC。
/////////////////////////////////////////////////////////////////////////////
我看了MSDN中qsort()如下：
void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );
compare( (void *) elem1, (void *) elem2 );
The routine must compare the elements, then return one of the following values:
Return Value Description
< 0 elem1 less than elem2
0 elem1 equivalent to elem2
> 0 elem1 greater than elem2
////////////////////////////////////////////////////////////
虽然cmp中确实是三种情况，但是我们平时写的时候都不是写全的，一样能达到
从小到大的排序。见以下资料：
一、对int类型数组排序
int num[100];
int cmp ( const void *a , const void *b )
{
return *(int *)a - *(int *)b;
}
qsort(num,100,sizeof(num[0]),cmp);
二、对char类型数组排序（同int类型）
char word[100];
int cmp( const void *a , const void *b )
{
return *(char *)a - *(int *)b;
}
qsort(word,100,sizeof(word[0]),cmp);
三、对double类型数组排序
double in[100];
int cmp( const void *a , const void *b )
{
return *(double *)a > *(double *)b ? 1 : -1;
}
qsort(in,100,sizeof(in[0]),cmp);
四、对结构体一级排序
struct Sample
{
double data;
int other;
}s[100]
//按照data的值从小到大将结构体排序
int cmp( const void *a ,const void *b)
{
return (*(Sample *)a).data > (*(Sample *)b).data ? 1 : -1;
}
qsort(s,100,sizeof(s[0]),cmp);
五、对结构体二级排序
struct Sample
{
int x;
int y;
}s[100];
//按照x从小到大排序，当x相等时按照y从大到小排序
int cmp( const void *a , const void *b )
{
struct Sample *c = (Sample *)a;
struct Sample *d = (Sample *)b;
if(c->x != d->x) return c->x - d->x;
else return d->y - c->y;
}
qsort(s,100,sizeof(s[0]),cmp);
六、对字符串进行排序
struct Sample
{
int data;
char str[100];
}s[100];
//按照结构体中字符串str的字典顺序排序
int cmp ( const void *a , const void *b )
{
return strcmp( (*(Sample *)a)->str , (*(Sample *)b)->str );
}
qsort(s,100,sizeof(s[0]),cmp);
附加一个完整点的代码，对字符串二维数组排序：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char s[2001][1001];
int cmp(const void *a, const void *b){
return strcmp((char *)a,(char *)b);
}
int main(){
int i,n;
scanf("%d",&n);
getchar();
for(i=0;i<n;i++) gets(s[i]);
qsort(s,n,1001*sizeof(char),cmp);
for(i=0;i<n;i++) puts(s[i]);
return 0;
}
//////////////////////////////////////////////////////////
我第二个代码 和 第三个代码在以前资料中有写到，但是 我用在此题目中不行。
我通过输入点实例，输出排序后的点，发现点的排序米问题（测试的点有10几个）。
有群友说可能是duoble类型的精确度的问题，所以此时的cmp函数必须把三种情况写全，
有些说可能是此题目的数据bug问题。。。。囧，我都糊涂了，弄得我以后都不敢用qsort()
到底是什么原因，导致这样的情况，希望知道的前辈指点一二。
在此非常感谢！
[解决办法]
qsort的比较函数是直接作为函数指针处理的所以慢。sort是模板函数，所以比较函数很容易inline优化深度要比qsort高。另外qsort是纯quicksort，sort是优化的quicksort，quicksort递归次数过多的时候会改用heapsort，所以实际时间复杂度更接近O(NlogN)
[解决办法]
