题目背景

希尔排序是第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

希尔排序法的基本思想是：先选定一个整数gap，把待排序数分成多个组，所有距离为gap的数分在同一组内，并对每一组内的数进行排序。然后，取不同的gap，重复上述分组和排序的工作。当到达gap=1时再做插入排序。

‌希尔排序的时间复杂度通常表示为O(n^(1.3-2))，希尔排序的时间复杂度范围较大。希尔排序是一种不稳定的排序算法。

注：本题为模板题，仅作为教学使用。

题目描述

输入一个数组的长度n和所有元素，将数组按从小到大的顺序排序。

第一行一个整数n(1≤n≤10000)；

第二行是n个不大于10000的正整数。

n个用空格分隔的整数，为排序后的数组。

5
2 3 1 5 2

1 2 2 3 5

时间1000ms，内存256MiB