考研数据结构——每日一题[希尔排序]

shell_sort希尔排序

//每组内的下标是等差数列
//c++中的sort是快排+插排 【当排序到<28时改为插入排序】
void shell_sort()  // 希尔排序【分组的插入排序】 不稳定（间隔d的分为一组）
{
    for (int d = n / 3; d; d = d == 2 ? 1 : d / 3) //特判2，等于2就用1,（最后要用1，而2时d/3=0，所以特判） 【d为分组跨度（此时初始每组3个元素）】
    {
        for (int start = 0; start < d; start ++ )//分为d组，每组成员之间间隔为d，组内插入排序
        {
            for (int i = start + d; i < n; i += d)//比较一组 
            {
                int t = q[i], j = i;//j存同一组内小的下标 
                while (d != 0 && q[j - d] > t) //d != 0时（j > start） && 做以下标间隔d的插入排序
                {
                    q[j] = q[j - d];
                    j -= d;
                }
                q[j] = t; 
            }
        }
    }
}

//科学家证明过 用除3分组O(n^(3/2)) 
void shell_sort() //用除2,分组 O(n^2) 
{
	for(int d = n / 2; d ;d /= 2 ) //分为d组，每组成员之间间隔为d，组内插入排序 
	{
		for(int start = 0;start < d; start ++)//比较d组   
		{
			for(int i = start + d ;i < n;i += d)//比较一组 
			{
				int t = q[i] , j = i; //j存同一组内小的下标 
				while(j > start && q[j - d] > t) //相隔为d的分为一组比较 
				{
					q[j] = q[j - d];//后移，下标小的赋值给下标大的
					j -= d;
				}
				q[j] = t;
			}
		}
	}
}