感觉问题出在快速排序的两个函数上，麻烦各位大佬看一下哪里出了问题。
#include "stdafx.h"
#include <vector>
#include <math.h>
#include <time.h>
#include<algorithm>
#include <iostream>
using namespace std;
struct point//存储点坐标的结构体
{
int index;
float x,y;
};
void Same(int n,int k,point X[])//查找相同的坐标
{
for(int i=0;i<n;i++)
{
if(X[k].x==X[i].x&&X[k].y==X[i].y)
{
X[k].x=(float)(rand()%10001);
X[k].y=(float)(rand()%10001);
Same(n,k,X);
}
}
}
void QuickSort1(point arr[], int left, int right)//快速排序
{
if (left<right)
{
int i=left,j=right;
point a;
a=arr[left];
while (i<j)
{
while(i<j&&arr[j].x>=a.x) // 从右向左找第一个小于x的数
j--;
if(i<j)
arr[i++].x=arr[j].x;
while(i<j&&arr[i].x<a.x) // 从左向右找第一个大于等于x的数
i++;
if(i<j)
arr[j--].x=arr[i].x;
}
arr[i].x=a.x;
QuickSort1(arr,left,i-1); // 递归调用
QuickSort1(arr,i+1,right);
}
}
void QuickSort2(point arr[], int left, int right)//快速排序
{
if (left<right)
{
int i=left,j=right;
point a;
a=arr[left];
while (i<j)
{
while(i<j&&arr[j].y>=a.y) // 从右向左找第一个小于x的数
j--;
if(i<j)
arr[i++].y=arr[j].y;
while(i<j&&arr[i].y<a.y) // 从左向右找第一个大于等于x的数
i++;
if(i<j)
arr[j--].y=arr[i].y;
}
arr[i].y=a.y;
QuickSort2(arr,left,i-1); // 递归调用
QuickSort2(arr,i+1,right);
}
}
float Distance(point a, point b)//求两点之间距离 !不能以distance命名，与函数模板重名，xutility文件会报错
{
float x=a.x-b.x;
float y=a.y-b.y;
return sqrt(x*x+y*y);
}
void closest(point X[], point Y[],int low,int high,point &a,point &b,float &min)//求最近点对及其距离，设置ab的目的是输出最近点对的坐标
{
int i,j,k,m;
point al,bl,ar,br;
float dl,dr;
if((high-low)==1) // n=2直接计算两个点之间的距离
{
a=X[low];
b=X[high];
min=Distance(X[low], X[high]);
}
else
{
if((high-low)==2) // 当n=3时直接计算
{
dl = Distance(X[low], X[low+1]);
dr = Distance(X[low], X[low+2]);
min = Distance(X[low+1], X[low+2]);
if((dl<=dr)&&(dl<=min))
{
a = X[low], b = X[low+1], min = dl;
}
else
{
if(dr<=min)
{
a=X[low];
b=X[low+2];
min=dr;
}
else
{
a=X[low+1];
b=X[low+2];
}
}
}
else // 当n>3时进行分治
{
point *SL = new point[(high-low)/2+1];
point *SR = new point[(high-low)/2];
m = (high-low)/2 + low; // 把x数组以m为界划分为两半
j = k = 0;
for(i=0; i<=high-low; i++)
{
if(Y[i].index<=m)
{
SL[j++] = Y[i]; // 收集左边子集中的最近点对
}
else
{
SR[k++] = Y[i]; // 收集右边子集中的最近点对
}
}
closest(X,SL,low, m, al, bl, dl); // 计算左边子集的最近点对
closest(X,SR,m+1, high, ar, br, dr);// 计算右边子集的最近点对
if(dl<dr)
{ // 组合步得到左右子集中点的最短距离d
a = al, b = bl, min = dl;
}
else
{
a = ar, b = br, min = dr;
}
point *Z = new point[high-low+1];
k = 0;
for( i=0; i<=high -low; i++) // 收集距离中线距离小于d的元素，保存到数组Z（因Y数组按y坐标递增排序，Z数组也一样）
{
if(fabs(X[m].x - Y[i].x)<min)//abs求整数绝对值
{
Z[k].x = Y[i].x, Z[k++].y = Y[i].y;
}
}
for( i=0; i<k; i++)
{
for( j=i+1; (j<k)&&(Z[j].y-Z[i].y<min); j++){ // 若前后两点y轴的距离超过d则不可能使距离小于d，退出
dl = Distance(Z[i], Z[j]); // 计算前后两点的距离
if(dl<min){ // 若小于min，则更新
a = Z[i], b = Z[j], min = dl;
}
}
}
delete SL;
delete SR;
delete Z;
}
}
}
void closest_pair(point X[], int n, point &a, point &b, float &min){
if(n<2){ // 当点集个数小于2时不存在最近点对
min= 0;
}else{
QuickSort1(X,0,n-1); // 对x数组进行递增排序
point *Y = new point[n]; // 初始化辅助点数组Y
for( int i = 0 ; i < n ;i ++){
Y[i].index = i;
Y[i].x = X[i].x;
Y[i].y = X[i].y;
}
QuickSort2(Y,0,n-1); // 对y数组进行递增排序
closest(X,Y,0,n-1,a,b,min); // 求亲密点对
min = sqrt(min); // 将得到的d开平方才是两点间真正的距离
delete Y;
}
}
void main()
{
int n;
cout<<"请输入点个数："<<endl;
cin>>n;
point *X=new point[n];
srand((int)time(0));
for(int i=0;i<n;i++)
{
X[i].x=(float)(rand()%10001);
X[i].y=(float)(rand()%10001);
}
//for(int j=0;j<n;j++)
// Same(n,j,X);
point a,b;
float min;
closest_pair(X,n,a,b,min);
if(n>=2)
{
printf("最近点对为：(%.0f,%.0f),(%.0f,%.0f) \n两点距离为：%.4f\n", a.x, a.y, b.x, b.y, min);
}
else{
printf("不存在最近点对！\n");
}
}
