【数据结构】排序基石：透彻掌握概念，手撕插入排序与希尔排序（附代码）

//先看一趟排序
void InsertSort(int* a,int n )
{
	int end;
	int tmp = a[end + 1];//先把end+1放入tmp
	//[0,end]有序 end+1位置插入进去,保持有序
	while (end >= 0)
	{
		if (tmp<a[end]) //只要end+1的值比end小就交换，然后end向前走 继续看看满不满足交换条件
		{
			a[end + 1] = a[end];
			--end;
		}
		else
		{
			break;//tmp>a[end] 就不用换了 跳出循环
		}
	}
	a[end + 1] = tmp;//最后把最开始a[end+1]的值放到end后边 也就是现在的[end+1]的位置
    //极端情况下end=-1时跳出循环,此时表达式依然成立a[0]=tmp
}

//明白了一趟是怎么走的,那整体就显而易见了
void InsertSort(int* a,int n )
{
    //[0.n-1]
	for (int i = 0; i < n - 1; i++)//让end从0开始 end是数组下标 n个数 下标是从0到n-1,所以end+1最大就取到n-1 因此end最大取n-2 故循环条件为i<n-1
	{
		int end;
		int tmp = a[end + 1];
		//[0,end]有序 end+1位置插入进去,保持有序
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

//还是先看一趟
void ShellSort(int* a, int n)
{
	int gap = 3;//假设gap为3
	int end = 0;//end从0开始 也就是第一组
	int tmp = a[end + gap];
//后续代码与插入排序差不多，只不过是把1换成了gap,核心不变
	while (end >= 0)
	{
		if (tmp < a[end])
		{
			a[end + gap] = a[end];
			end -= gap;
		}
		else
		{
			break;
		}
	}
	a[end + gap] = tmp;

}

//套上循环就完成了一组的排序
void ShellSort(int* a, int n)
{
	int gap = 3;
	
	for (int i = 0; i < n - gap; i += gap)//这里取n-gap与上边插入排序的n-1同理
	{
		int end = i;
		int tmp = a[end + gap];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + gap] = a[end];
				end -= gap;
			}
			else
			{
				break;
			}
		}
		a[end + gap] = tmp;
	}

}

//套上循环就完成了一组的排序
void ShellSort(int* a, int n)
{
	int gap = 3;
	for(int j=0;j<gap;j++)//一共gap组
    {
         for (int i = 0; i < n - gap; i += gap)
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (tmp < a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }

}

void ShellSort(int* a, int n)
{
	int gap = 3;
	
	for (int i = 0; i < n - gap; i++)//把这里改成i++就可以了
	{
		int end = i;
		int tmp = a[end + gap];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + gap] = a[end];
				end -= gap;
			}
			else
			{
				break;
			}
		}
		a[end + gap] = tmp;
	}

}

void ShellSort(int* a, int n)
{
	int gap = n;;
	
	while (gap > 1)
	{
		//+1保证最后一个gap一定是1
		//gap>1时是预排序
		//gap==1时 是插入排序
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i += gap)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}

}