很早之前就看到一道关于螺钉螺母的ACM题目的。最近又看了“分治法”的思想，于是强迫自己去把这个代码写出来！
题目如下：
给你一堆螺母和螺帽，每个螺母都有一个相对应的螺帽，但是他们之间的对应关系已经打乱。你可以比较螺母和螺帽的大小关系，但是你无法比较螺母和螺母的大小关系，你也无法比较螺帽和螺帽的大小关系。设计一个算法，找出螺母和螺帽的对应关系。
当然，我肯定是冲着时间复杂度nlogn去的。否则就暴力解法了。
思路如下：螺母我就用nut表示，螺钉我就用bolt表示。方便区别，否则螺母螺钉的叫，都叫混了……
我是假设只有唯一一个匹配的，即nut数组与bolt一一对应。否则算法还需要有更大的更改。
1.在nut数组拿一个，可以把bolt数组分为比那个小的，比那个大的，还有一个匹配的3个部分。
2.在bolt中小的那堆那一个可以把nut分成比那个小的，比那个大的，还有一个匹配的3个部分。
3.这样可以发现，现在数组产生两对比配的螺母和螺钉和一队小的螺钉和螺母，一队大的螺钉和螺母。
如图所示：
我令数组内部的排列也是这样。一次调用后前两个是匹配的螺母和螺钉。后面给一个坐标，左边是小的，右边是较大的。
这样我对较小的螺母和螺钉再调用一个次函数，即又可以产生两对匹配，和较小小和较大大的。呵呵！
说到这里，可以发现这个跟快速排序的原理很相似。
先上几个辅助函数：
//交换指定的两个元素 void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } //打印指定数组 void Print(int *a) { for (int i = 0; i < 9; i++) { cout << a[i] << " "; } cout << endl; }
方便调试使用。
下面是正文：
//分类函数 //n和b为两个数组 //left为左索引，right为右索引 void Fix(int *n, int *b, int left, int right) { if (left < right) { int tmp = n[left]; int i = left, j = right; while (i < j) { while (i < j&&b[i] < tmp) { i++; } while (i < j&&b[j] > tmp) { j--; } if (i < j) { swap(b[i], b[j]); } } b[i] = tmp; swap(b[left], b[i]); cout << "n+b:" << endl; Print(n); Print(b); cout << endl; //一趟下来，i=j的tmp的位置。以tmp为界限，左右分别是小于和大于它的元素 tmp = b[left + 1]; i = left + 1, j = right; while (i < j) { while (i < j&&n[i] < tmp) { i++; } while (i < j&&n[j] > tmp) { j--; } if (i < j) { swap(n[i], n[j]); } } n[i] = tmp; swap(n[left + 1], n[i]); cout << "n+b:" << endl; Print(n); Print(b); cout << endl; Fix(n, b, left + 2, i); Fix(n, b, i + 1, right); } }
根据之前说的思想写的。首先对上面的数组进行分组，再对下面的数组分组。
最后递归调用两遍Fix函数。从left+2到i，因为已经有两组匹配了，所有left+2，i是分界点。
另一组自然就是i+1到right了。
测试用例为：
int nut[9] = { 5, 9, 3, 7, 1, 8, 2, 4, 6 }; int bolt[9] = { 7, 4, 1, 2, 5, 6, 9, 8, 3 }; Fix(nut, bolt, 0, 8);
函数调用过程为：
