[数据结构与算法]C解OJ题--存在重复元素（采用折半插入排序）

前言：
??此处先声明一点，本排序专栏的OJ题，不出意外情况都会采用数据结构中的各种经典排序算法，目的是巩固排序算法。所以使用的方法比较复杂的话，不要介意。
??当然排序算法种类比较多，一个OJ题不可能全部实现一遍，因此每个排序的OJ题，会采用其中的一种方法来实现。
??其次各种排序方式在排序专栏中都有详细介绍，所以在这些OJ题中只会初略提及，不会详述。

??插入排序有三类： 直接插入排序，折半插入排序，希尔排序。
??此处采用折半插入排序来解这道OJ题

原题如下：

??给定一个整数数组，判断是否存在重复元素。
??如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

简单思路：
??先采用排序手段对该组数据进行排序，排序后再对这组数据进行遍历判断。

折半插入排序思想：
??折半插入排序与直接插入排序的不同点是，直接插入排序边比较边移动位置，而折半插入排序是先采用二分查找找到要插入的位置，之后再进行移动。其相对于直接插入排序减少了比较的次数，从而使效率提高。

代码实现：

bool containsDuplicate(int* nums, int numsSize){
    int i;//用于标记有序组元素下标
    int j;//用于标记无序组元素下标
    int high;//用于标记有序组中的高端地址
    int mid;//用于标记有序组中的中端地址
    int low;//用于标记有序组中的低端地址
    int temp;//临时变量，用于临时存储数据
    for(j=1;j<numsSize;j++)//依次从无序组中取出数据
    {
        temp=nums[j];//将数据进行备份
        high=j-1;//高端地址为无序组第一个数据位置的前一个位置，即有序组的最后一个数据位置
        low=0;//低端地址为有序组的第一个数据位置
        while(low<=high)//如果low>high,则low所标记的位置将是要插入的位置
        {
            mid=(high+low)/2;
            if(temp>nums[mid])//插入位置在中端位置的右边
            {
                low=mid+1;//low指向中端位置的下一个位置
            }
            else//插入位置在中端位置的左边
            {
                high=mid-1;//high指向中端地址的上一个位置
            }
        }
        for(i=j-1;i>=low;i--)//将low所指的当前数据及后面的数据整体移动一个位置
        {
             nums[i+1]=nums[i];
        }
        nums[low]=temp;
    }
    for(i=1;i<numsSize;i++)//进行遍历判断
    {
        if(nums[i-1]==nums[i])return true;//判断是否存在重复元素
    }
    return false;
}

??我是老胡，感谢阅读！！ ?? ??