螺母和螺栓问题

给出了不同螺母的列表和螺栓的列表。我们的任务是从给定的列表中找到螺母和螺栓的正确匹配，并在匹配时将螺母分配给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
End

nutAndBoltMatch（螺母，螺栓，低，高）

输入：螺母列表，螺栓列表，数组的上下索引。

输出：显示哪个螺母用于哪个螺栓。

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: ! # $ % & ( ) * @ ^