算法——递归与分治之最接近点对问题

给定平面上n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对的距离最小。
1.一维的情况

package com.yuxh.nearestPoints; import java.util.Collections; import java.util.LinkedList; import java.lang.Math; import com.yuxh.util.SimplePrint; /** * @author YuXH * @version $Revision: 1.0 $, $Date: 2008/04/22 16:27:55 $ */ public class NearestPoints { /* * 求一维点集s的最接近点对的算法 */ public int cpair1(int s[]) { int d = 1000; if (s.length == 2) { d = Math.abs(s[0] - s[1]); } else if (s.length == 1) { d = 1000; } else { // m = s中各点的中位数 // 构造s1和s2 int s1[] = new int[(s.length + 1) / 2]; int s2[] = new int[s.length / 2]; int midDivArray[] = midDiv(s); for (int i = 0; i < midDivArray.length; i++) { if (i < (midDivArray.length + 1) / 2) {// 构造s1 s1[i] = midDivArray[i]; } else {// 构造s2 s2[i - ((s.length + 1) / 2)] = midDivArray[i]; } } SimplePrint.print("s1: ", s1); SimplePrint.print("s2: ", s2); int d1 = cpair1(s1); int d2 = cpair1(s2); int p = max(s1); int q = min(s2); int res[] = { d1, d2, q - p }; d = min(res); } System.out.println("d: " + d); return d; } /* * 求s中的最大元素 */ private int max(int s[]) { LinkedList list = new LinkedList(); for (int i = 0; i < s.length; i++) { list.add(s[i]); } return Collections.max(list); } /* * 求s中的最小元素 */ private int min(int s[]) { LinkedList list = new LinkedList(); for (int i = 0; i < s.length; i++) { list.add(s[i]); } return Collections.min(list); } /* * 求中位数 */ private int[] midDiv(int inputArray[]) { int midLoc = inputArray.length / 2; for (int i = 0; i < inputArray.length; i++) { if (i < midLoc) { if (inputArray[i] > inputArray[midLoc]) { // 交换 int temp = inputArray[i]; inputArray[i] = inputArray[midLoc]; inputArray[midLoc] = temp; } } else { if (inputArray[i] < inputArray[midLoc]) { // 交换 int temp = inputArray[i]; inputArray[i] = inputArray[midLoc]; inputArray[midLoc] = temp; } } } return inputArray; } public static void main(String[] args) { NearestPoints np = new NearestPoints(); int testArray[] = { 2, 10, 6, 79, 15, 68, 45, 66, 75 }; SimplePrint.print("origenal array: ", testArray); System.out.println("End of d: " + np.cpair1(testArray)); } }