C解OJ题--两个数组的交集（希尔排序+双指针）

前言：
  本次排序专题的这道OJ题，我们采用希尔排序+双指针的思路来解答。一起来巩固一下希尔排序与双指针吧。

原题如下：

  给定两个数组，编写一个函数来计算它们的交集。
审题：
   题目所要求的就是找出两个数组中它们都有的数据，叫做交集，并且它们的交集是去重的，并返回它们的交集。
  有一个重要的点是交集中的数据是不重复的，即我们要去掉重复元素。

思路分析：
  将两组数据进行排序，排序后采用双指针判断（排序+双指针）
  也就是如果现在有两组数组数据如下：

  我们对其采用排序手段进行排序，排序后如下：

  排序完成后，开辟一个数组空间，数组空间大小为原两数组中的较大者。再利用双指针的思想进行比较判断如下：

  比较数组一和数组二的当前位置，如果两者数据相同，并且在新数组中没有这个数据，则将其加入到新数组中。

希尔排序：
  其实本题的重点是考察排序，这这里我们采用经典排序算法中的希尔排序。
  我们都知道希尔排序相比折半插入排序和直接插入排序都更加的高效，因为希尔排序不仅降低了比较的次数，还降低了移动的次数。

思想：
  先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

步骤：
 1.分组。分组的间隔通常会找总长度的一半左右；
 2.组内进行排序。采用直接插入排序对各组内成员进行排序；
 3.重新设置间隔分组。将间隔变为原来的一半（Shell建议的序列）；
 4.直到间隔为1。对整个数据进行直接插入排序。

  最后给出我们按照希尔排序+双指针对本OJ题的代码实现。

代码实现：

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
   int increment;//标记增量
   int temp;//发生逆序时用于存储数据的临时变量
   int i;//标记各组
   int j;//标记各组内数据元素
   for(increment=nums1Size/2;increment>0;increment/=2)//对nums1进行希尔排序，增量每次变为原来二分之一
   {
       for(i=increment;inums1[i-increment])continue;
           temp=nums1[i];
           for(j=i;j>=increment&&temp0;increment/=2)//对nums2进行排序
   {
       for(i=increment;inums2[i-increment])continue;
           temp=nums2[i];
           for(j=i;j>=increment&&tempnums2Size?nums1Size:nums2Size;//新数组取决于两者中的较大者
   int*result=(int*)malloc(sizeof(int)*size);//开辟数组空间
   *returnSize=0;
   while(inums2[j])j++;
       else if(nums1[i] 
  有关希尔排序的更多细节实现，如果有兴趣的请查看我往期文章对希尔排序的分享。
 
 
  我是老胡，感谢阅读！！❤️ ❤️
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5650589.html