最近在看Sedgewick的那本Algorithms in C++，里面在28章有一个关于最近距离的点队的问题求解的算法，分析研究了2天还是有所疑惑，有几个点比较以后，拿出来请教大家，希望能给以一些分析。
主要算法：
算法的主要思想是先比较x坐标，然后比较y坐标，然后用合并排序来选择距离最小的点对：
主要的数据结构，点和链表节点：
struct point
{
    int x;
    int y; 
};

struct node
{
    struct point p;
    struct node *next;
};
//全局变量
/* global */
int pass; // 表明比较x还是y坐标
struct node *z; // 尾节电，无限大
float min; // 最短距离
struct point cp1, cp2; // 最短距离点对

//坐标比较函数，pass为一比较x坐标，否则（2）比较y坐标：

int comp(struct node *t)
  { return (pass == 1) ? t->p.x : t->p.y; }
//合并排序函数
struct node *merge(struct node *a, struct node *b)
  {
    struct node *c; 
    c = z;
    do
      if (comp(a) < comp(b)) 
        { c->next = a; c = a; a = a->next; }
      else
        { c->next = b; c = b; b = b->next; }
    while (c != z);
    c = z->next; z->next = z;
    return c;
  }
//距离比较函数

void check(struct point p1, struct point p2)
{
    float dist;
    if ((p1.y != z->p.y) && (p2.y != z->p.y))
    {
        dist = sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
        if (dist < min)
        {
            min = dist; cp1 = p1; cp2 = p2;
        }
    }
}


// 主要核心比较函数
struct node *sort(struct node *c, int number)
{
    static int sort_i = 0;
    int i;
    struct node *a, *b, *tt;
    float middle;
    struct point p1, p2, p3, p4;
    if (c->next == z)
        return c;
    a = c;
    for (i = 2; i <= number/2; i++)
        c = c->next;
    b = c->next;
    c->next = z;
    if (pass == 2)
    {
        middle = b->p.x;
    }
    //按照Sedgewick的说法,在调用这个merge之前,链表是以x坐标排好序的.
    c = merge(sort(a, number/2), sort(b, number - (number/2)));
    //按照Sedgewick的说法,在这个merge之后, midlle的左右两半的内部点之间的距离,都大于min
    // 这是为什么?
    //为什么这里要比较四个点,为什么四个点足够了,这又是为什么?
    if (pass == 2)
    {
        p1 = z->p; p2 = z->p; p3 = z->p; p4 = z->p;
        for (a = c; a != z; a = a->next)
            if (fabs(a->p.x - middle) < min)
            {
                check(a->p, p1);
                check(a->p, p2);
                check(a->p, p3);
                check(a->p, p4);
                p1 = p2; p2 = p3; p3 = p4; p4 = a->p;
            }
    }
    return c;
}


//主函数

int main()
{
z = new node; z->p.x = max; 
              z->p.y = max; z->next = z;
h = new node; h->next = readlist();
min = max;
//第一次pass为1，对x坐标排序
pass = 1; h->next = sort(h->next, N);
//第二次pass为2，对y坐标排序
pass = 2; h->next = sort(h->next, N);
}