【排序算法全家桶 Level 1】插入排序：从“手动摸牌”到“神速希尔”。

void InsertSort(int* a, int n)
{
    // n 是数组的总长度，i 只需要走到 n-2 的位置
    // 因为待插入的元素是 a[i+1]，当 i = n-2 时，a[i+1] 正好是最后一个元素 a[n-1]
    for (int i = 0; i < n - 1; i++)
    {
        int end = i;          // [0, end] 是已经排好序的区间
        int tmp = a[end + 1]; // 拿出待插入的那个“新牌”

        // 在有序区间 [0, end] 中寻找 tmp 的合适位置
        while (end >= 0)
        {
            if (a[end] > tmp) // 如果前面的牌比新牌大
            {
                a[end + 1] = a[end]; // 把前面的牌往后挪一个位置
                end--;               // 继续往前看
            }
            else
                // 找到了！此时 a[end] <= tmp，说明 tmp 应该插在 end 的后面
                break; 
        }
        // 插入 tmp。注意：由于循环内 end 减了1，所以实际位置是 end + 1
        a[end + 1] = tmp; 
    }
}

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		// 每次缩小 gap。+1 是为了确保最后一次循环 gap 必定等于 1
		gap = gap / 3 + 1;

        // 这里是多组并排：i 每次自增 1，处理的是当前 gap 下的所有逻辑分组
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap]; // 拿出本组中的下一个元素

			while (end >= 0)
			{
                // 注意：你提供的代码中此处逻辑是 (tmp > a[end])，这将实现【从大到小】排序
                // 如果需要普通的从小到大排序，请改为 (a[end] > tmp)
				if (tmp > a[end]) 
				{
					a[end + gap] = a[end]; // 组内挪动
					end -= gap;            // 步长为 gap
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}