排序（2）（希尔排序）

1.插入排序的时间复杂度：最坏为从1到n的等差数列之和。也就是n的平方，但最好为n

2.希尔排序的思路：

    1.预排序（接近有序）：  假设gap为一组，总计gap组，对gap组分别插入排序

    2.插入排序

3.两种循环思路实现第一步预处理：即将所有数据分成gap组，gap越大大的数越快到后面，小的数越快到前面，gap越小挪动越慢越接近有序gap越大和越小时解决o(n)，gap=1时是直接插入排序，并在组内完成插入排序

代码实现：注释部分为另一种循环思路

void shellsort(int* a, int n)
{
    int gap=3;
    //for (int j = 0; j < gap; j++)
    //{
    //
    //     for (int i = j; i < n - gap; i = i + gap)
    for(int i=0;i<n-gap;i++)
        {
            int end = n;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (a[end] > tmp)
                {
                    a[end + gap] = a[end];
                    end = end - gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;//第一个位置
        }
    //}
    }
    

  以上即为分组插入的思路，而gap的核心写法为：

void shellsort(int* a, int n)
{
    int gap=n;
while(gap>1)
    //for (int j = 0; j < gap; j++)
    //{
    //
    //     
{
gap=gap/3+1;
for (int i = j; i < n - gap; i = i + gap)
    for(int i=0;i<n-gap;i++)
        {
            int end = n;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (a[end] > tmp)
                {
                    a[end + gap] = a[end];
                    end = end - gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;//第一个位置
        }
    //}
    }

}
    

效果为不断趋近于有序,时复为gap*(1+2+......n/gap),约为log3n到log2n之间