Python版希尔排序算法实现与效率比较

算法描述：

希尔排序算法是插入法排序的改进，其思路是对原始数据进行分组，把相距k（称为增量）个位置的数据分为一组并在组内使用插入法排序，k的初始值为数据数量的二分之一并且每次减半，最终为1。插入法排序中元素的移动距离始终为1，在希尔排序算法中元素可以长距离移动，可以获得更高的效率，希尔排序算法的时间复杂度为O(n^1.5)，而插入排序算法的时间复杂度为O(n^2)。但元素的长距离移动导致希尔排序算法的不稳定性，即在某种意义下相等的元素可能无法保持其相对顺序。

参考代码：

运行结果：