### 问题描述 希尔排序是直接插入排序算法的一种更高效的改进版本，但它是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出的改进方法之一： 1. 插入排序在对几乎已经排好序的数据操作时，效果是非常好的。 2. 插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。 而通常对于希尔排序中我们选择增量序列为：$\left\lfloor \frac{N}{2} \right\rfloor, \left\lfloor \frac{N}{4} \right\rfloor, ..., 1$，其中 $N$ 为待排序数组的长度。 现在，给你一个整数数组，要求使用希尔排序算法对它进行排序。 ### 输入格式 第一行是一个整数 $n$，表示整数数组的长度。 第二行包含 $n$ 个空格分隔的整数 $a_1,a_2,...a_n$。 ### 输出格式 输出 $n$ 个整数，即从小到大排序后的数组。 ### 样例输入 ``` 5 5 2 9 1 5 ``` ### 样例输出 ``` 1 2 5 5 9 ``` ### 测评数据规模 对于 $100$% 的数据，$n \leq 10^5$，整数的绝对值不超过 $10^9$。