一、问题
给定平面上N个点的坐标，找出距离最近的两个点。
分析：
输入：N个点，即N组坐标（N >= 2），每个坐标可以用数据结构Point结构体来表示，存储x和y坐标。
输出：两个点，即2组坐标。
约束：输出的两个点在输入所有的点中距离最近。
附加：可以把最小距离值也作为一个输出。
思考：
可以先考虑一维情况下问题的解，在拓展处理二维情况（平面）。
二、一维解法
我们先从输入数据为一维情况下入手，此时考虑的问题是：N个数中两两差值绝对值对小的两个点。这里N个数采用长度为N的数组来存储。在一维解法中尝试拓展到二维情况。
解法一：暴力求解法
思想：枚举任意两个数差值绝对值，求解最小值。
时间复杂度：O(n^2)。
拓展：拓展到二维平面情况，枚举平面上任意两各点之间距离，可求解最近点对，时间复杂度仍然为O(n^2)。
算法C实现：
/**
* @brief find value_a and value_b that they have the minimum distance in
* the array.
*
* @param[in] array element array
* @param[in] array_size element array size
* @param[out] value_a element a
* @param[out] value_b element b
*
* @return return the minimum distance between value_a and value_b
*/
ElementType find_closest_array(ElementType* array, CommonType array_size,
ElementType* value_a, ElementType* value_b)
{
assert(array != NULL && value_a != NULL &&
value_b != NULL && array_size >= 2);
/// initialize values.
ElementType distance_min = abs(array[0] - array[1]);
*value_a = array[0];
*value_b = array[1];
/// find closest value_a and value_b by violent
CommonType i, j;
ElementType temp;
for (i = 0; i < array_size; i++) {
for (j = i + 1; j < array_size; j++) {
if ((temp = abs(array[i] - array[j])) < distance_min) {
*value_a = array[i];
*value_b = array[j];
distance_min = temp;
}
}
}
/// return minimum distance
return distance_min;
}
解法二：排序算法+线性查找
思想：首先对数组进行排序（如果无序），采用快速排序、归并排序、堆排序等算法时间复杂度为O(n*lgn)；再计算N-1对相邻两点的距离，找到最小值，时间复杂度为O(n)。
时间复杂度：O(n*lgn) + O(n) = O(n*lgn)。
拓展：在二维平面上，不论是利用点的x轴数据排序还是y轴数据排序，都不能保证相邻点对的距离值就是最小的，必须枚举所有情况(O(n^2)才可知道，因此这种解法不能拓展到二维情况。
算法C实现：
1.排序算法采用快速排序算法实现，对数组进行从小到大排序；
2.排序后因为知道前后大小关系不需要计算绝对值，直接做差求得两数差值绝对值。
/**
* @brief select the last element as a pivoit.
* Reorder the array so that all elements with values less than the pivot
* come before the pivot, while all elements with values greater than the pivot
* come after it (equal values can go either way). After this partitioning, the
* pivot is in its final position.
*
* @param[in,out] array input and output array
* @param[in] index_begin the begin index of the array(included)
* @param[in] index_end the end index of the array(included)
*
* @return the position of the pivot(index from the array)
*/
CommonType partition(ElementType* array, CommonType index_begin,
CommonType index_end)
{
/// pick last element of the array as the pivot
ElementType pivot = array[index_end];
/// index of the elments that not greater than pivot
CommonType i = index_begin - 1;
CommonType j, temp;
/// check array's elment one by one
for (j = index_begin; j < index_end; j++) {
if (array[j] <= pivot) {
/// save the elements not greater than pivot to left index of i.
i++;
temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
/// set the pivot to the right position
array[index_end] = array[++i];
array[i] = pivot;
/// return the position of the pivot
return i;
}
/**
* @brief quick sort method for input array from index_begin to index_end.
*
* @param[in,out] array input and output array
* @param[in] index_begin the begin index of the array(included)
* @param[in] index_end the end index of the array(included)
*/
void quick_sort(ElementType* array, CommonType index_begin,
CommonType index_end)
{
/// sort only under the index_begin < index_end condition
if ( index_begin < index_end) {
/// exchange elements to the pivot position by partition function
CommonType index_pivot = partition(array, index_begin, index_end);
/// sort the array before the pivot position
quick_sort(array, index_begin, index_pivot - 1);
/// sort the array after the pivot position
quick_sort(array, index_pivot + 1, index_end);
}
}
/**
* @brief find value_a and value_b that they have the minimum distance in
* the array.
*
* @param[in] array element array
* @param[in] array_size element array size
* @param[out] value_a element a
* @param[out] value_b element b
*
* @return return the minimum distance between value_a and value_b
*/
ElementType find_closest_array(ElementType* array, CommonType array_size,
ElementType* value_a, ElementType* value_b)
{
assert(array != NULL && value_a != NULL &&
value_b != NULL && array_size >= 2);
/// initialize values.
ElementType distance_min = array[1] - array[0];
*value_a = array[1];
*value_b = array[0];
/// find closest value_a and value_b by sort
quick_sort(array, 0, array_size - 1);
CommonType i;
ElementType temp;
for (i = 1; i < array_size - 1; i++) {
if ((temp = array[i + 1] - array[i]) < distance_min) {
*value_a = array[i];
*value_b = array[i + 1];
distance_min = temp;
}
}
/// return minimum distance
return distance_min;
}
解法三：排序算法+分治算法
思想：采用分治思想，把排序后的数组从中间值分为左右两个部分，最小距离值两个点要么都来自左半部分，有么来自右半部分，要么是来自左半部分的最大值点和来自右半部分的最小值点。
注意：这个算法在一维情况下时间复杂度总体上不如上面的解法二，但是这个算法的解决思路可以拓展到二维情况并解决二维情况下问题，而解法二不可拓展到二维情况。
时间复杂度：O(n*lgn)（排序算法）+ O(n*lgn)（分治算法）= O(n*lgn)。
算法C实现：
注意：
输入是已经排好序的数组，可以先调用快速排序算法对数组进行排序。
实现时考虑为把中间值定位数组中间的数据，并且左半部分子数组不含该数据，右半部分子数组含该数据。
跨越两个子数组的最小距离值直接求得，最后三个距离值做比较，跨越数组的距离值并不考虑用左半和右半得到的最小距离作为阈值排除，因为一维情况下会显的繁琐（二维情况下有必要）。
算法实现核心思想是分治思想：分解、解决、合并。
/**
* @brief find value_a and value_b that they have the minimum distance in
* the array.
*
* @param[in] array element array
* @param[in] index_begin element array index begin(included)
* @param[in] index_end element array index end(included)
* @param[out] value_a element a
* @param[out] value_b element b
*
* @return return the minimum distance between value_a and value_b
*/
ElementType find_closest_array(ElementType* array, CommonType index_begin,
CommonType index_end, ElementType* value_a, ElementType* value_b)
{
assert(array != NULL && value_a != NULL && value_b != NULL);
ElementType distance_left, distance_middle, distance_right;
CommonType left_value_a, left_value_b, right_value_a, right_value_b,
middle_value_a, middle_value_b;
if (index_begin + 1 < index_end) {
/// array length is larger than 2
CommonType middle_index = index_begin +
((unsigned)(index_end - index_begin) >> 1);
/// left sub-array
distance_left = find_closest_array(array, index_begin, middle_index - 1,
&left_value_a, &left_value_b);
/// right sub-array
distance_right = find_closest_array(array, middle_index, index_end,
&right_value_a, &right_value_b);
distance_middle = array[middle_index] - array[middle_index - 1];
/// middle distance
middle_value_a = array[middle_index];
middle_value_b = array[middle_index - 1];
/// get minimum distance and value_a, value_b
if (distance_left < distance_right) {
if (distance_middle < distance_left) {
*value_a = middle_value_a;
*value_b = middle_value_b;
return distance_middle;
} else {
*value_a = left_value_a;
*value_b = left_value_b;
return distance_left;
}
} else {
if (distance_middle < distance_right) {
*value_a = middle_value_a;
*value_b = middle_value_b;
return distance_middle;
} else {
*value_a = right_value_a;
*value_b = right_value_b;
return distance_right;
}
}
} else if (index_begin + 1 == index_end) {
/// array length is 2, only get one distance
*value_a = array[index_begin];
*value_b = array[index_end];
return array[index_end] - array[index_begin];
} else {
/// array length is 1, can not the distance
*value_a = INT_MAX;
*value_b = INT_MAX;
return INT_MAX;
}
}
三、二维解法
这里考虑从上面一维解法中解法三拓展出来的解法。
分解子问题：在二维平面上，我们采用分治思想，把N个点分为左右数量近似相等的左右两部分（数量相等保证子问题均衡），具体实现时：利用点横坐标值对N个点进行排序，取排序后的中点，作为分界线，中点可以放到左部分或右部分其中一个，此时左右部分点个数相等或只差1。这样可以分别求解左右部分的最近点对及距离值，该问题为子问题，还需要处理的特殊的情况是最近点对可能是一个点位于左部分而另一个点位于右部分，综合这3个局部最优解，就可以得到N个数的最优解即最近点对。
特殊问题处理：考虑最近点对可能是一个点位于左部分而另一个点位于右部分这种情况。一种解法是枚举所有情况找最优，此时有N/2 * N/2种情况，效率较低。另一种解法是：先计算得出左右部分最近点对最优解（两个距离值中最小的一个距离值d），在分界线L左右两端考虑这个距离值d范围内的点（增加约束一）；对这些点进行纵坐标排序（可以事先对所有点进行纵坐标排序，避免多次排序）（增加约束二），只考虑纵坐标差值绝对值也小于这个距离值的相邻点对（否则点对距离值必然大于上述距离值d）。分析：这些点个数最多为6个，此时6个点为下面图中两个边界重合正方形6个顶点。
时间复杂度：O(n*lgn)。
算法C实现：
1.求出N个点分别按横坐标和纵坐标排序后的序列。
2.排序算法要求能够对数组按照给定的比较方法（横坐标排序或纵坐标排序）以及特定的数据结构（点Point数据结构）进行排序，因此需要优化解法二中的快速排序算法使之更具有通用性（接口参考标准库qsort函数），便于扩展。这里直接使用标准函数库排序算法。
3.建立结构体点Point
四、拓展问题