python 希尔排序

　　原理

　　希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

　　希尔排序是基于插入排序的以下两点性质而提出改进方法的：

　　插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率

　　但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

　　步骤

　　每次以一定步长(就是跳过等距的数)进行排序，直至步长为1.

　　代码

　　def shell_sort(list):

　　n = len(list)

　　# 初始步长

　　gap = n // 2

　　while gap > 0:

　　for i in range(gap, n):

　　# 每个步长进行插入排序

　　temp = list[i]

　　j = i

　　# 插入排序

　　while j >= gap and list[j - gap] > temp:

　　list[j] = list[j - gap]

　　j -= gap

　　list[j] = temp

　　# 得到新的步长

　　gap = gap // 2

　　return list

　　步长使用的是Donald Shell的建议，另外步长还可以使用Sedgewick提出的(1, 5, 19, 41, 109,…)。

　　也可以使用斐波那契数列除去0和1将剩余的数以黄金分区比的两倍的幂进行运算得到的数列。

　　以上内容为大家介绍了python 希尔排序，希望对大家有所帮助，如果想要了解更多Python相关知识，请关注多测师。https://www.e70w.com/xwzx/