python 希尔排序

发布时间:2022-05-09 09:52:11 人气:37 作者:多测师

  原理

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

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

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

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

  步骤

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

python 希尔排序

  代码

  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/


上一篇:python 插入排序
下一篇:python 归并排序
返回列表
在线客服
联系方式

热线电话

17727591462

上班时间

周一到周五

二维码
线