...
 Algorithms

『ShellSort』详解「希尔排序」的Python实现

...
hokyo
发布于 4 年, 1 ヶ月 之前
1500
0

希尔排序

希尔排序，其实就是插入排序的亚种。
亚种就是取步长，步长为1的时候，那么就是一个插入排序。
希尔排序理解起来比较难，网上有很多解释。这里有几个参考的网页。

顺便补充2个豆知识，Python移位运算符。

>>右移 表示2进制下的移位，就是变小小。这个需要自己查一下哦。
8 >> 1 其实 8 * 2-1 就是除2了 print(8 >> 1) # 4
8 >> 2 其实 8 * 2-2 就是除4了 print(8 >> 2) # 2

<<左移 表示2进制下的向左移位，就是变大大。这个需要自己查一下哦。
8 << 1 其实 8 * 21 就是乘以2了 print(8 << 1) # 16
8 << 2 其实 8 * 22 就是乘以4了 print(8 << 2) # 32

关于Python 的整除问题。
在Python2里面，/ 整数会去掉小数点，浮点数会保留。
而//在2，3里没有区别。所以我们接下来的代码都用了//。

Python2 Python3
/ 整数会去掉小数点
浮点数会保留
print(3/2) # 1
print(3.0/2) # 1.5
print(4/2) # 2
print(4.0/2) # 2.0		 全部都是float类型
print(3/2) # 1.5
print(3.0/2) # 1.5
print(4/2) # 2.0
print(4.0/2) # 2.0
// 没区别 int出来是int，float出来是float
print(3//2) # 1
print(3.0//2) # 1.0		 没区别 int出来是int，float出来是float
print(3//2) # 1
print(3.0//2) # 1.0

代码实现

代码参考链接 参考网页：希尔排序 

def shellSort(arr):    
    n = len(arr)    
    # 这里的gap取什么是根据你的实际状况取最优，为了展示方便，选择了取半    
    gap = n // 2    
    while gap > 0:    
        for i in range(gap,n):    
            j = i    
            while j > 0:  
                # 到这里就很插入有不一样的地方了，对比的不是-1，而是减去步长  
                if arr[j] < arr[j-gap]:    
                    arr[j], arr[j-gap] = arr[j-gap], arr[j]  
                    # 这里也是同理  
                    j -= gap    
                else:    
                    break  
        # 然后在进行分组 直到 while的gap不是为0为止              
        gap //= 2     
    return arr    

arr = [66,4,8,90,13,6,-9]    
print(shellSort(arr))

希尔排序并不是排序的重点，主要利用的是插入排序的思想。其中最难理解的就是为什么要取步长的问题。
这个就是一个通过分组优化插入排序的过程。

#Python #算法 #希尔排序

共有评论(0)

登陆即可评论哦