Merge Sort

void mergeSort(int *sortedArr, int start, int end)
{
    if(start == end)
    {
        return;
    }
   
    int mid = (int)((start + end) / 2);
    mergeSort(sortedArr, start, mid);
    mergeSort(sortedArr, mid + 1, end );
    int *tempArr = new int[end - start + 1];
    int i = start;
    int j = mid + 1;
    int k = 0;
    while(i <= mid && j <= end)
    {
        if(sortedArr[i] < sortedArr[j])
        {
            tempArr[k] = sortedArr[i];
            i++; k++;
        }
        else
        {
            tempArr[k] = sortedArr[j];
            j++; k++;
        }
    }
    if(i == mid + 1)
    {
        for(; j <= end; j++, k++)
            tempArr[k] = sortedArr[j];
    }
    else
    {
        for(; i <= mid; i++, k++)
            tempArr[k] = sortedArr[i];
    }
    k = 0;
    for(int i = start; i <= end; i++, k++)
        sortedArr[i] = tempArr[k];
    delete[] tempArr;
}

Quick Sort 快排

void quickSort(int* a, int start, int end)
{
    if(start == end)
        return;
    int key = a[start];
    int keyIndex = start;
    int i = start, j = end;
    int backward = 1;
    int temp;
    while(i != j)
    {
        if(backward)
        {
            for(; j > i; j--)
            {
                if(a[j] < key)
                {
                    temp = a[j];
                    a[j] = a[i];      //a[i]  == key
                    a[i] = temp;
                    keyIndex = j;
                    break;
                }
            }
            backward = 0;
        }
        else
        {
            for(; i < j; i++)
            {
                if(a[i] > key)
                {
                    temp = a[j];       //a[j]  == key
                    a[j] = a[i];
                    a[i] = temp;
                    keyIndex = i;
                    break;
                }
            }
            backward = 1;
        }
    }
    quickSort(a, start, keyIndex);
    if(keyIndex != end)
        quickSort(a, keyIndex + 1, end);
}

递归求square root

设要求根的数为n, 定义f(x) = x^2 - n

应用Newton's Method估算 f(x) = 0 的正数解。首先猜测X[0] (X[0] > 0)为方程的解，之后根据recurrence relation: X[i] = X[i-1] - f(X[i-1]) / f''(X[i-1]) = (X[i-1] + n / X[i-1]) / 2 使X[i]不断逼近准确解。 当误差小于一定范围时，返回当前估算值。

double sqrtRecursive(double n, double guess)
{
     if(abs(guess * guess - n) < 0.00001)
         return guess;
     else
         return sqrtRecursive(n, (guess + n/guess)*0.5);
}

和为n连续正数序列

题目：输入一个正数n，输出所有和为n连续正数序列。不考虑一个数的序列。
例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。 

注意： 由于序列至少有两个元素且连续，所以序列起始元素最大不超过(int)(n/2), 结束元素最大不超过(int)(n/2) + 1, 因此无需遍历 1...n-1。

方法1.

使用枚举的方法，两个for循环可以搞定。时间复杂度O(n^2)。

void CountinousSequenceSum_1(int n)
{
    if(n < 3)
        return;

    int sum;

    for(int i = 1; i < n/2 + 1; i++)
    {
        sum = i;
        for(int j = i + 1; j < n/2 + 2; j++)
        {
            sum += j;
            if(sum == n)
            {
                for(int k = i; k < j + 1; k++)
                    cout << k << " ";
                cout << endl;
            }
        }
    }

    return;
} 

方法2.

因为整数序列是有序的，可以设立两个游标small,big，通过判区间[small,big]的和是
否为N来得到这个序列。如果区间和大于n,small往前移动，如果小于 n,big往前移动，等于就输出
这个区间。时间复杂度是0(n)。

void CountinousSequenceSum_2(int n)
{
    if(n < 3)
        return;

    int start = 1, end = 2;
    int sum = start + end;
   
    while(end < n/2 + 2)
    {
        if(sum == n)
        {
            for(int i = start; i < end + 1; i++)
                cout << i << " ";
            cout << endl;
            end++;
            sum += end;
        }
        else if(sum > n)
        {
            sum -= start;
            start++;
        }
        else
        {
            sum += end + 1;
            end++;
        }
    }
}

递归法求字符串的全排列 (permutation)

每次递归调用，解决一个当前元素数量为n-k ( k = 0...n-1)的全排列，为解决当前当前排列,　又需要递归解决n-k个元素数量为n-k-1的全排列

举例：字符串abc, n = 3, []中的元素为需要计算排列的元素集，[]外的元素为已经确定排列顺序的元素

                                   [abc]         
     /             |             \
               a[bc]          b[ac]          c[ba]
              /        |         /        \         |        \
  ab[c]   ac[b]   ba[c]   bc[a]  cb[a]   ca[b]
     |            |            |            |            |            |
  abc       acb       bac       bca     cba      cab

第一层：k = 0，1个全排列需解决，为此需解决3个元素数为2的全排列
第二层：k = 1，3个全排列需解决，解决每个全排列需要解决2个元素数为1的全排列
第三层：k = 2，6个全排列需解决，解决每个全排列需要解决2个元素数为0的全排列（说明当前层已解得所需的所有全排列）
第四层：k = 3， k等于n，到达递归底层，打印当前排列

static void RecursivePermute(char* str,int k)//递归函数

{

     int i;

     if(k==strlen(str))

          printf("%s\n",str);

     else

     {

          for(i=k;i<strlen(str);i++)

          {

               ExchangeCharacters(str,k,i);

               RecursivePermute(str,k+1);

               ExchangeCharacters(str,k,i);

          }

     }

}

static void ExchangeCharacters(char* str, int p1,int p2)

{

     char tmp;

     tmp=str[p1];

     str[p1]=str[p2];

     str[p2]=tmp;

}

<转>线性时间排序算法：Radix Sort

基数排序(Radix Sort) 算法的基本思想是，在待排序列里，分别从低位到高位依次排序，这样最后整个序列就有序了。例如，序列329,57,657,839,436 排序过程是这样的：

3 2 9 0 5 7 6 5 7 8 3 9 4 3 6      ^

=>

4 3 6 0 5 7 6 5 7 3 2 9 8 3 9   ^

=>

3 2 9 4 3 6 8 3 9 0 5 7 6 5 7 ^

=>

0 5 7 3 2 9 4 3 6 6 5 7 8 3 9

这样看似更麻烦了，本来只需要排一次的东西现在要排好几次了，其实，这个主要是为了减轻上面1所讲的技术排序的限制，例如，如果一个序列里的数的范围很大，是2^32或者2^64，那么这个序列就无法用计数排序(Counting Sort)了，但是，如果用基数排序，每一轮用一次计数排序，总得时间复杂度是m*O(n)=O(n)。我们还可以根据内存等条件的具体情况，可以每2位或者3位作为一个单位进行排序。

这个算法要注意的一点是：排序时必须从后往前排，并且各个数字必须对齐。

<转>线性排序算法：Counting Sort

计数排序的限制条件是：所排对象的各个元素都是介于0--k的，并且这个k不是无限的，是在有限的内存里能用数组表示的。

计数排序的基本思想是，当读到一个数时，如果能确定出比这个元素小的数的个数，那这个数应该排的位置自然就知道了。为了实现这个目标，计数排序引入了2个辅助数组，B和C。假设原数组是A，长度为n，数组B的长度也是n；假设每个元素的范围是0--k，那数组C的长度就是k。例如，已知我有一组数 2 5 3 0 2 3 0 3，所有数的范围都在0---5之间，那我们的数组C声明就应该是int C[6];

然后具体做法就是，遍历一遍A，读入一个数，就在对应C的位置+1，例如，读入一个数2，就让 C[2]++，这样，读完一遍以后就知道各个数出现了多少次。然后对C进行整理，得出比这个数小的有多少个(或者将这个数视为该数在排序后序列中应该存放的位置index，比如C[i] = 3,　则有3个数比A[i]小，A[i]应存在b[3]，即排序后的第4个位置上)，整理办法如下：

// assume C[0..k]

for i = 1 .. k do:

    C[i] = C[i-1] + C[i]

最后得出了各个数都有多少个比它小的个数以后，就可以进行最后的排序了：

遍历A，读入一个数x后就去C里找他应该放的位置，即C[x]的值就是他应该放的位置，放入B数组的该位置中，然后对应的C[x]-- (因为考虑到可能有重复的数)。

for i = 0 .. n do:

       x = A[i]

       index = C[x]

       B[index] = x

       C[x]--

最长公共子序列 (LCS = Longest Common Subsequence) 和最长公共子串 (LCS = Longest Common Substring)

两个序列a,b, L[i][j]为以a[i]和b[j]结尾的最长公共子序列的长度。a长度为m, b长度为n

Longest Common Subsequence (子序列无需连续）

Initial condition:
L[0][j] = (a[0] == b[j]) ? 1 : 0     j = 0...n
L[i][0] = (a[i] == b[0]) ? 1 : 0     i = 0...m
Recurrence relation:
L[i][j] = (a[i] == b[j])  ? L[i-1][j-1] + 1 : max(L[i][j-1], L[i-1][j])    i = 1...m, j = 1...n

最后L[m][n]即为结果

 Longest Common Substring（子串需要连续）

Initial condition:
a[0][j] = (a[0] == b[j]) ? 1 : 0     j = 0...n
a[i][0] = (a[i] == b[0]) ? 1 : 0     i = 0...m
Recurrence relation:
L[i][j] = (a[i] == b[j])  ? L[i-1][j-1] + 1 : 0   i = 1...m, j = 1...n结果为计算过程中最大的L[i][j] (用一个max变量跟踪）

最长单调递增子序列（LIS）

最长单调递增子 序列，就是在一个数列中最长的按单调递增的顺序排列的序列，该序列在原序列中可以不连续。

解法1:

设b[i]为截止到第i个数且以第i个数为结尾的最长单调递增子序列的长度，a为所给序列，则有：

Initial condittion:
b[0]  = 1
Recurrence relation:

b[ i ] = max( a[i] > a[j] ? b[j] + 1 : 1)    j = 0...i-1

//return value: length of LIS
//aMax: LIS array
//a: original array
//b: b[i] stores the length of the local LIS with the last member a[i]
//p: p[i] stores the previous index of member of the local LIS with the last member a[i]

int LIS(int *a, int *b, int *p, int *aMax, int n)
{
    int max = 0;
    int maxIndex;

    for(int i = 0; i < n; i++)
    {
        b[i] = 1;
        for(int j = 0; j < i; j++)
        {
            if(a[i] > a[j] && b[i] < b[j] + 1)
            {
                b[i] = b[j] + 1;
                p[i] = j;
            }
        }

        if(b[i] > max)
        {
            max = b[i];
            maxIndex = i;
        }
    }

    for(int i = max -1; i > -1;  i--)
    {
        aMax[i] = a[maxIndex];
        maxIndex = p[maxIndex];
    }

    return max;
}

复杂度o(n2)

解法2:

将原序列按升序排序，再对原序列和排序后的序列计算LCS(Longest Common Subsequence）的长度。

排序复杂度o(nlogn), LCS复杂度o(n2), 总复杂度o(n2)

最长连续数字序列， 计数并输出

 int longestNumString(char *string, char *output)
{
    int count = 0;
    int max = 0;
    char *start;
    char *startMax;

    while(true)
    {
        if(*string >= '0' && *string <= '9')
            start = string;

        while(*string >= '0' && *string <= '9' && *string)
        {
            string++;
            count++;
        }

        if(count > max)
        {
            max = count;
            startMax = start;
        }

        count = 0;

        if(*string)
            string++;
        else
            break;
    }

    for(int i = 0; i < max; i++)
    {
        *output = *startMax;
        startMax++;
        output++;
    }

    return max;
}

<转>Count the number of bits that are on in an unsigned integer（计算一个无符整数中1Bit的个数）

计算一个无符号整数中有多少的Bit为1
原创整理，转载请注明出处。
这是一个经常遇到的经典问题，这里分两个部分讲解和总结，首先对讲解现有的算法，然后再讲解一些改进算法。

1．循环法（Iterated Count）

int bitcount (unsigned int n)  

{

int count=0;      

    while (n)  {

        count += n & 0x1u ;

        n >>= 1 ;

      }

return count ;

}

最容易理解和想到的方法。对每一位依次判断是否为1，如果是就在count上加1。
循环的次数是常数（n的位数）。在1比较稀疏的时候效率低，可用方法2改进。
2．Bit1稀疏 Sparse Ones

int bitcount (unsigned int n)  

{

int count=0 ;

         while (n)  {

         count++ ;

         n &= (n - 1) ;

     }

     return count ;

}

理解这个算法的核心，只需理解2个操作：
1> 当一个数被减1时，他最右边的那个值为1的Bit将变为0，同时其右边的所有的Bit都会变成1。
2>“&=”，位与并赋值操作。去掉已经被计数过的1，并将改值重新设置给n.
这个算法循环的次数是bit位为一的个数。也就说有几个Bit为1，循环几次。对Bit为1比较稀疏的数来说，性能很好。如：0x1000 0000, 循环一次就可以。

3．密集1的算法 Dense Ones

int bitcount (unsigned int n)

{

     int count = 8 * sizeof(int) ;

     n ^= (unsigned int) -1 ;

     while (n)

    {

        count-- ;

        n &= (n - 1) ;

     }

     return count ;

}

4．8bit静态表查找法 Precompute_8bit

      static int bits_in_char [256] = {

    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2,

    3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3,

    3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,

    4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,

    3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5,

    6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4,

    4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,

    6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,

    3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3,

    4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6,

　6, 7, 6, 7, 7, 8

};

   int bitcount (unsigned int n)     
   {
      int count = 8 * sizeof(int) ;
      n ^= (unsigned int) -1 ;
      while (n)
      {
         count-- ;
         n &= (n - 1) ;
      }
      return count ;
   }
 

使用静态数组表，列出所有8bit(256个)无符号数含有Bit1的个数。将32Bit 的n分4部分，直接在表中找到对应的Bit1的个数，然后求和。

这是最快的方法了。缺点是需要比较大的内存。

更多方法参见http://blog.csdn.net/jemmy/archive/2009/07/29/4390278.aspx

reverse bits

翻转一个char的8个bits

char bitReverse(char a)
{
 char b = 0;
 for(int i = 0; i < 8; i++)
 {
  if(a & 1)
   b = b | (1 << (7 - i));
  a = a >> 1;
 }
 return b;
}

<转>最大子序列的线性时间算法

Int MaxSubsequenceSum(const int A[], int N)
{
       int ThisSum, MaxSum, j;
       ThisSum = MaxSum = 0;
       For(j=0; j < N; j++)
       {
              ThisSum += A[j];
              If (ThisSum > MaxSum)
                     MaxSum = ThisSum;
              Else if(ThisSum < 0)
                     ThisSum = 0;
       }
       return MaxSum;
}

对于这个算法的分析(逻辑):

从左相右相加，若结果不断的增加，那么ThisSum将同MaxSum一起增加，如果遇到负数，那么也加到ThisSum上去，但是此时ThisSum < MaxSum，那么就不加。看ThisSum是不是会回升，若一直不回升，不断或是波浪型的下降，那么当它降到0时，说明前一段与后一段是可以抛弃的。正如有 7 ， -8 一样，我们可以不要这两个数，但是我们知道MaxSum依然保存着前一段的最大值，（这就是这个算法中的厉害，我认为）。然后，ThisSum将从后面开始将这个子段进行分析，若有比当前MaxSum大的子段，然后替换（此时可以彻底抛弃前一段）。这样一趟扫描结果也就出来了。

在序列中所有数都是负数的情况下不能用该算法，结果会返回0。考虑到这种情况，在应用此算法前只需增加一次遍历判断值是否都为负，是则返回序列中最大值，否则应用上面的算法，复杂度仍然是o(n)。

<转>最接近点对问题

　　这个问题很容易理解，似乎也不难解决。我们只要将每一点与其他n-1个点的距离算出，找出达到最小距离的两个点即可。然而，这样做效率太低，需要O(n²)的计算时间。在问题的计算复杂性中我们可以看到，该问题的计算时间下界为Ω(nlogn)。这个下界引导我们去找问题的一个θ(nlogn)算法。

    这个问题显然满足分治法的第一个和第二个适用条件，我们考虑将所给的平面上n个点的集合S分成2个子集S₁和S₂，每个子集中约有n/2个点，·然后在每个子集中递归地求其最接近的点对。在这里，一个关键的问题是如何实现分治法中的合并步骤，即由S₁和S₂的最接近点对，如何求得原集合S中的最接近点对，因为S₁和S₂的最接近点对未必就是S的最接近点对。如果组成S的最接近点对的2个点都在S₁中或都在S₂中，则问题很容易解决。但是，如果这2个点分别在S₁和S₂中，则对于S₁中任一点p，S₂中最多只有n/2个点与它构成最接近点对的候选者，仍需做n²/4次计算和比较才能确定S的最接近点对。因此，依此思路，合并步骤耗时为O(n²)。整个算法所需计算时间T(n)应满足:　

T(n)=2T(n/2)+O(n²)

    它的解为T(n)=O(n²)，即与合并步骤的耗时同阶，显示不出比用穷举的方法好。从解递归方程的套用公式法，我们看到问题出在合并步骤耗时太多。这启发我们把注意力放在合并步骤上。

    为了使问题易于理解和分析，我们先来考虑一维的情形。此时S中的n个点退化为x轴上的n个实数x₁,x₂,..,x_n。最接近点对即为这n个实数中相差最小的2个实数。我们显然可以先将x₁,x₂,..,x_n排好序，然后，用一次线性扫描就可以找出最接近点对。这种方法主要计算时间花在排序上，因此如在排序算法中所证明的，耗时为O(nlogn)。然而这种方法无法直接推广到二维的情形。因此，对这种一维的简单情形，我们还是尝试用分治法来求解，并希望能推广到二维的情形。

    假设我们用x轴上某个点m将S划分为2个子集S₁和S₂，使得S₁={x∈S|x≤m}；S₂={x∈S|x>m}。这样一来，对于所有p∈S₁和q∈S₂有p

    递归地在S₁和S₂上找出其最接近点对{p₁,p₂}和{q₁,q₂}，并设δ=min{|p₁-p₂|,|q₁-q₂|}，S中的最接近点对或者是{p₁,p₂}，或者是{q₁,q₂}，或者是某个{p₃,q₃}，其中p₃∈S₁且q₃∈S₂。如图1所示。

图1 一维情形的分治法

    我们注意到，如果S的最接近点对是{p₃,q₃}，即|p₃-q₃|<δ，则p₃和q₃两者与m的距离不超过δ，即|p₃-m|<δ，|q₃-m|<δ，也就是说，p₃∈(m-δ,m]，q₃∈(m,m+δ]。由于在S₁中，每个长度为δ的半闭区间至多包含一个点（否则必有两点距离小于δ），并且m是S₁和S₂的分割点，因此(m-δ,m]中至多包含S中的一个点。同理，(m,m+δ]中也至多包含S中的一个点。由图1可以看出，如果(m-δ,m]中有S中的点，则此点就是S₁中最大点。同理，如果(m,m+δ]中有S中的点，则此点就是S₂中最小点。因此，我们用线性时间就能找到区间(m-δ,m]和(m,m+δ]中所有点，即p₃和q₃。从而我们用线性时间就可以将S₁的解和S₂的解合并成为S的解。也就是说，按这种分治策略，合并步可在O(n)时间内完成。这样是否就可以得到一个有效的算法了呢？还有一个问题需要认真考虑，即分割点m的选取，及S₁和S₂的划分。选取分割点m的一个基本要求是由此导出集合S的一个线性分割，即S=S₁∪S₂ ，S₁∩S₂⁼Φ，且S₁{x|x≤m}；S₂{x|x>m}。容易看出，如果选取m=[max(S)+min(S)]/2，可以满足线性分割的要求。选取分割点后，再用O(n)时间即可将S划分成S₁={x∈S|x≤m}和S₂={x∈S|x>m}。然而，这样选取分割点m，有可能造成划分出的子集S₁和S₂的不平衡。例如在最坏情况下，|S₁|=1，|S₂|=n-1，由此产生的分治法在最坏情况下所需的计算时间T(n)应满足递归方程:

   T(n)=T(n-1)+O(n)

    它的解是T(n)=O(n²)。这种效率降低的现象可以通过分治法中“平衡子问题”的方法加以解决。也就是说，我们可以通过适当选择分割点m，使S₁和S₂中有大致相等个数的点。自然地，我们会想到用S的n个点的坐标的中位数来作分割点。在选择算法中介绍的选取中位数的线性时间算法使我们可以在O(n)时间内确定一个平衡的分割点m。

    至此，我们可以设计出一个求一维点集S中最接近点对的距离的算法CPAIR1如下。

function CPAIR1(S);
begin
  if |S|=2 then δ=|x[2]-x[1]| // x[1..n]存放的是S中n个点的坐标
           else if (|S|=1) 
                   then δ:=∞
                   else begin
                          m:=S中各点的坐标值的中位数;
                          构造S1和S2,使S1={x∈S|x≤m}，S2={x∈S|x>m};
                          δ1:=CPAIRI(S1);
                          δ2:=CPAIRI(S2);
                           p:=max(S1);
                           q:=min(S2);
                          δ:=min(δ1,δ2,q-p);
                        end;
  return(δ);
end;

    由以上的分析可知，该算法的分割步骤和合并步骤总共耗时O(n)。因此，算法耗费的计算时间T(n)满足递归方程：

    解此递归方程可得T(n)=O(nlogn)。

    这个算法看上去比用排序加扫描的算法复杂，然而这个算法可以向二维推广。

    下面我们来考虑二维的情形。此时S中的点为平面上的点，它们都有2个坐标值x和y。为了将平面上点集S线性分割为大小大致相等的2个子集S₁和S₂，我们选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S₁={p∈S|p_x≤m}和S₂={p∈S|p_x>m}。从而使S₁和S₂分别位于直线l的左侧和右侧，且S=S₁∪S₂ 。由于m是S中各点x坐标值的中位数，因此S₁和S₂中的点数大致相等。

    递归地在S₁和S₂上解最接近点对问题，我们分别得到S₁和S₂中的最小距离δ₁和δ₂。现设δ=min(δ₁,δ₁)。若S的最接近点对(p,q)之间的距离d(p,q)<δ则p和q必分属于S₁和S₂。不妨设p∈S₁，q∈S₂。那么p和q距直线l的距离均小于δ。因此，我们若用P₁和P₂分别表示直线l的左边和右边的宽为δ的2个垂直长条，则p∈S₁，q∈S₂，如图2所示。

图2 距直线l的距离小于δ的所有点

    在一维的情形，距分割点距离为δ的2个区间(m-δ,m](m,m+δ]中最多各有S中一个点。因而这2点成为唯一的末检查过的最接近点对候选者。二维的情形则要复杂些，此时，P₁中所有点与P₂中所有点构成的点对均为最接近点对的候选者。在最坏情况下有n²/4对这样的候选者。但是P₁和P₂中的点具有以下的稀疏性质，它使我们不必检查所有这n²/4对候选者。考虑P₁中任意一点p,它若与P₂中的点q构成最接近点对的候选者，则必有d(p,q)<δ。满足这个条件的P₂中的点有多少个呢？容易看出这样的点一定落在一个δ×2δ的矩形R中，如图3所示。

图3 包含点q的δ×2δ的矩形R

由δ的意义可知P₂中任何2个S中的点的距离都不小于δ。由此可以推出矩形R中最多只有6个S中的点。事实上，我们可以将矩形R的长为2δ的边3等分，将它的长为δ的边2等分，由此导出6个（δ/2）×（2δ/3）的矩形。如图4(a)所示。

图4 矩形R中点的稀疏性

    若矩形R中有多于6个S中的点，则由鸽舍原理易知至少有一个δ×2δ的小矩形中有2个以上S中的点。设u,v是这样2个点，它们位于同一小矩形中，则

    因此d(u,v)≤5δ/6<δ 。这与δ的意义相矛盾。也就是说矩形R中最多只有6个S中的点。图4(b)是矩形R中含有S中的6个点的极端情形。由于这种稀疏性质，对于P₁中任一点p，P₂中最多只有6个点与它构成最接近点对的候选者。因此，在分治法的合并步骤中，我们最多只需要检查6×n/2=3n对候选者，而不是n²/4对候选者。这是否就意味着我们可以在O(n)时间内完成分治法的合并步骤呢？现在还不能作出这个结论，因为我们只知道对于P₁中每个S₁中的点p最多只需要检查P₂中的6个点，但是我们并不确切地知道要检查哪6个点。为了解决这个问题，我们可以将p和P₂中所有S₂的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S₂中点一定在矩形R中，所以它们在直线l上的投影点距p在l上投影点的距离小于δ。由上面的分析可知，这种投影点最多只有6个。因此，若将P₁和P₂中所有S的点按其y坐标排好序，则对P₁中所有点p，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者，对P₁中每一点最多只要检查P₂中排好序的相继6个点。

    至此，我们可以给出用分治法求二维最接近点对的算法CPAIR2如下:

function CPAIR2(S);
begin
  if |S|=2 then δ:=S中这2点的距离
     else if |S|=0 
           then δ:=∞
           else begin
                 1.  m:=S中各点x坐标值的中位数;
                     构造S1和S2，使S1={p∈S|px≤m}和S2={p∈S|px>m}
                 2.  δ1:=CPAIR2(S1);δ2:=CPAIR2(S2);
                 3.  δm:=min(δ1,δ2);
                 4.  设P1是S1中距垂直分割线l的距离在δm之内的所有点组成的集合，
                     P2是S2中距分割线l的距离在δm之内所有点组成的集合。将P1和
                     P2中的点依其y坐标值从小到大排序，并设P1*和P2*是相应的已排
                     好序的点列;
                 5.  通过扫描P1*以及对于P1*中每个点检查P2*中与其距离在δm之内的
                     所有点(最多6个)可以完成合并。当P1*中的扫描指针逐次向上移动
                     时，P2*中的扫描指针可在宽为2δm的一个区间内移动。设δl是按
                     这种扫描方式找到的点对间的最小距离;
                 6.  δ=min(δm,δl);
               end;
  return(δ);
end;

    下面我们来分析一下算法CPAIR2的计算复杂性。设对于n个点的平面点集S，算法耗时T(n)。算法的第1步和第5步用了O(n)时间，第3步和第6步用了常数时间，第2步用了2T(n/2)时间。若在每次执行第4步时进行排序，则在最坏情况下第4步要用O(nlogn)时间。这不符合我们的要求。因此，在这里我们要作一个技术上的处理。我们采用设计算法时常用的预排序技术，即在使用分治法之前，预先将S中n个点依其y坐标值排好序，设排好序的点列为P^*。在执行分治法的第4步时，只要对P^*作一次线性扫描，即可抽取出我们所需要的排好序的点列P₁^*和P₂^*。然后，在第5步中再对P₁^*作一次线性扫描，即可求得δ_l。因此，第4步和第5步的两遍扫描合在一起只要用O(n)时间。这样一来，经过预排序处理后的算法CPAIR2所需的计算时间T(n)满足递归方程：

    显而易见T(n)=O(nlogn)，预排序所需的计算时间为O(n1ogn)。因此，整个算法所需的计算时间为O(nlogn)。在渐近的意义下，此算法已是最优的了。

　　若有多种点求不同种点间的最接近点对，该方法不适用, 由于无法找到合适的bounding, 对于每一个点无法只检测常数个点 ,merging部分时间复杂度大于o(n),　因此无法在0(nlogn)时间内完成。