python排序算法——希尔排序（附代码）

---

一、前言

相关知识来自《python算法设计与分析》。初级排序算法是指几种较为基础且容易理解的排序算法。初级排序算法包括插入排序、选择排序和冒泡排序3种。相比起初级排序算法高级排序算法往往有更加复杂的逻辑但也会有更高的时间或空间效率。其中有些高级排序算法是由初级排序算法优化而来的。

二、算法描述

希尔排序又叫“缩小增量排序”是对插入排序进行优化后产生的一种排序算法。它的执行思路是把数组内的元素按下标增量分组对每一组元素进行插入排序后缩小增量并重复之前的步骤直到增量到达1。

一般来说希尔排序的时间复杂度为O(n1.3)～O(n2)它视增量大小而定。希尔排序的空间复杂度是O(1)它是一个不稳定的排序算法。进行希尔排序时元素一次移动可能跨越多个元素从而可能抵消多次移动提高了效率。

下面是使用数组长度/2作为初始增量的升序希尔排序每一轮排序过后增量都缩小一半。第一步如图2-28所示从第一个元素开始以增量4来分组。可以看出当增量为4时一组内只有两个元素否则元素的下标就超出了数组的范围。

第二步如图2-29所示对组内的元素进行插入排序。

第三步如图2-30所示继续用相同的方法分组对组内的元素进行插入排序使得它们有序。

整个数组内的数都被遍历完成后这一轮排序就结束了。把增量缩小一半继续进行下一轮排序。

第四步如图2-31所示增量为2时可以看出每一组内的元素增多了组的总数减少了。继续对每一组内的元素进行插入排序直到每一组都遍历完成。

第五步最后一轮排序如图2-32所示再次把增量缩小一半这时增量为1相当于对整个数组进行插入排序也就是最后一轮排序。

最后一轮排序结束后整个希尔排序就结束了。

三、代码实现

在for循环中由于每组的第一个元素不用进行插入排序而它们的下标处于0～step-1所以从下标step开始遍历。

需要注意的是如果要模拟流程图中的做法要使用两个循环先分组然后一次性使同组内的元素有序。为了提高效率我们直接使用一个for循环每遍历到一个数就对它所在的组进行插入排序。这样遍历同样符合插入排序的顺序要求。在插入排序中要改变当前下标的值所以使用变量ind存储当前下标防止影响for循环。

普通插入排序等同于增量为1的希尔排序跨元素的希尔排序实际上只改变了增量逻辑上与普通插入排序没有区别。

希尔排序代码

nums = [5,3,6,4,1,2,8,7]
def ShellSort(nums):
  step = len(nums)//2　　　　　　　　 #初始化增量为数组长度的一半
  while step > 0:　　　　　　　　　　 #增量必须是大于0的整数
   for i in range(step,len(nums)):　#遍历需要进行插入排序的数
     ind = i
     while ind >= step and nums[ind] < nums[ind-step]: #对每组进行插入排序
      nums[ind],nums[ind-step] = nums[ind-step],nums[ind]
      ind -= step
   step //= 2　　　　　　　　　　　#增量缩小一半
  print(nums)
ShellSort(nums)

运行程序输出结果为

[1,2,3,4,5,6,7,8]

---

总结

以上就是本文要讲的内容本文介绍了希尔排序的理论知识和代码实现。一般来说希尔排序的时间复杂度为O(n1.3)～O(n2)它视增量大小而定。希尔排序的空间复杂度是O(1)它是一个不稳定的排序算法。