螺母和螺栓问题
给出了不同螺母的列表和螺栓的列表。我们的任务是从给定的列表中找到螺母和螺栓的正确匹配，并在匹配时将螺母分配给Bolt。
快速排序技术解决了这个问题。通过将螺栓的最后一个元件作为枢轴，重新排列螺母列表，并获得以螺栓为枢轴元件的螺母的最终位置。对螺母列表进行分区后，我们可以使用所选螺母对螺栓列表进行分区。对左右子列表执行相同的任务以获取所有匹配项。
输入输出
Input:
The lists of locks and keys.
nuts = { ),@,*,^,(,%, !,$,&,#}
bolts = { !, (, #, %, ), ^, &, *, $, @ }
Output:
匹配螺母和螺栓后：
Nuts: ! # $ % & ( ) * @ ^
Bolts: ! # $ % & ( ) * @ ^算法
分区（数组，低，高，枢轴）
输入：一个数组，低和高索引，枢轴元素。
输出： 枢轴元素的最终位置。
Begin
i := low
for j in range low to high, do
if array[j] < pivot, then
swap array[i] and array[j]
increase i by 1
else if array[j] = pivot, then
swap array[j] and array[high]
decrease j by 1
done
swap array[i] and array[high]
return i
EndnutAndBoltMatch（螺母，螺栓，低，高）
输入：螺母列表，螺栓列表，数组的上下索引。
输出：显示哪个螺母用于哪个螺栓。
Begin pivotLoc := partition(nuts, low, high, bolts[high]) partition(bolts, low, high, nuts[pivotLoc]) nutAndBoltMatch(nuts, bolts, low, pivotLoc-1) nutAndBoltMatch(nuts, bolts, pivotLoc + 1, high) End
示例
#include<iostream>
using namespace std;
void show(char array[], int n) {
for(int i = 0; i<n; i++)
cout << array[i] << " ";
}
int partition(char array[], int low, int high, char pivot) { //find location of pivot for quick sort
int i = low;
for(int j = low; j<high; j++) {
if(array[j] <pivot) { //when jth element less than pivot, swap ith and jth element
swap(array[i], array[j]);
i++;
}else if(array[j] == pivot) { //when jth element is same as pivot, swap jth and last element
swap(array[j], array[high]);
j--;
}
}
swap(array[i], array[high]);
return i; //the location of pivot element
}
void nutAndBoltMatch(char nuts[], char bolts[], int low, int high) {
if(low < high) {
int pivotLoc = partition(nuts, low, high, bolts[high]); //choose item from bolt to nut partitioning
partition(bolts, low, high, nuts[pivotLoc]); //place previous pivot location in bolt also
nutAndBoltMatch(nuts, bolts, low, pivotLoc - 1);
nutAndBoltMatch(nuts, bolts, pivotLoc+1, high);
}
}
int main() {
char nuts[] = {')','@','*','^','(','%','!','$','&','#'};
char bolts[] = {'!','(','#','%',')','^','&','*','$','@'};
int n = 10;
nutAndBoltMatch(nuts, bolts, 0, n-1);
cout << "匹配螺母和螺栓后："<< endl;
cout << "Nuts: "; show(nuts, n); cout << endl;
cout << "Bolts: "; show(bolts, n); cout << endl;
}输出结果
匹配螺母和螺栓后： Nuts: ! # $ % & ( ) * @ ^ Bolts: ! # $ % & ( ) * @ ^