20191209-八大排序之希尔排序

yuanran0 2019-12-09

1. 希尔排序

算法核心思想

希尔排序本质也是一种插入排序,但是是根据简单插入排序进行优化后的一种更加高效的版本,别称缩小增量排序。希尔排序的核心思想是将排序数组按照步长进行分组,然后对分组的元素进行直接插入排序,循环缩小分组步长,最后当步长长度为1的时候排序结束。希尔排序在数组中采用的是跳跃式分组的策略,通过某个增量将数组元素划分为若干组,然后分组进行插入排序,随后逐步缩小增量,继续按组进行插入排序操作,直至增量为1。具体逻辑如下:

  1. 设定初始步长为gap=len(arr)//2
  2. 按照步长遍历列表元素,比如数组长度为8,则步长为4,分组如下:

a)     第一组,第一个元素和第五个元素,下标分别是0,4

b)     第二组,第二个元素和第六个元素,下标分别是1,5

c)     第三组,第三个元素和第七个元素,下标分别是2,6

d)     第四组,第四个元素和第八个元素,下标分别是3,7

  1. 缩短步长,gap=gap//2
  2. 按照新的步长遍历列表元素,步长为2,分组如下:

a)     第一组,第一,三,五,七个元素,下标分别为0,2,4,6

b)     第二组,第二,四,六,八个元素,下标分别为1,3,5,7

  1. 缩短步长,gap=gap//2

a)     第一组,第一,二,三,四,五,六,七个元素,下标为0,1,2,3,4,5,6,7

代码实现

普通实现01

def myShellInsertSort(arr):
    gap = len(arr)//2#初始步长
    while gap>=1:
        for i in range(gap,len(arr)):
            for j in range(i-gap,-1,-gap):
                if arr[j+gap]<arr[j]:
                    arr[j],arr[j+gap]=arr[j+gap],arr[j]
            print()
        gap//=2
    return arr
print(myShellInsertSort(s))

普通实现02

def myShellInsertSort(arr):
    gap = len(arr)//2#初始步长
    while gap>=1:
        for i in range(gap,len(arr)):
            temp = arr[i]
            j = i
            while j>=gap and arr[j-gap]>temp:
                arr[j] = arr[j-gap]
                j-=gap
            arr[j] = temp
            print(arr)
        gap //= 2  # 缩小增量为原始增量的一半
    return arr
print(myShellInsertSort(s))

普通实现03

def myShellInsertSort(arr):
    gap = len(arr)//2#初始步长
    while gap>=1:
        for i in range(gap,len(arr)):
            for j in range(i,gap-1,-gap):
                if arr[j]<arr[j-gap]:
                    arr[j],arr[j-gap] = arr[j-gap],arr[j]
        gap //= 2  # 缩小增量为原始增量的一半
    return arr
print(myShellInsertSort(s))

执行解析

设定初始步长gap=len(arr)//2,以步长从0-gap位置遍历arr,如果发现相邻元素的大小相反,则调整位置,此处的相邻元素是指第i个元素和第i-gap个元素。

总结

希尔排序是一种不稳定的排序

希尔排序的时间性能优于直接插入排序的原因:

  1. 当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
  2. 当n值较小时,n和n2的差别也较小,即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0( n2)差别不大。
  3. 在希尔排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量di逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按di-1作为距离排过序,使文件较接近于有序状态,所以新的一趟排序过程也较快。

希尔排序适合中型规模的数组,人们相继提出了很多种增量方式,其中最具代表性的是Hibbard增量和Sedgewick增量。

  1. Hibbard的增量序列如下:

1,3,7,15......通项公式 2^k-1利用此种增量方式的希尔排序,最坏时间复杂度是O(n^(3/2))

  1. Sedgewick的增量序列如下:

1, 5, 19, 41, 109......通项公式 9*4^k - 9*2^k + 1 或者 4^k - 3*2^k + 1

利用此种增量方式的希尔排序,最坏时间复杂度是O(n^(4/3))

相关推荐

yishujixiaoxiao / 0评论 2019-10-21