排序算法(三):希尔排序

希尔排序是插入排序的升级版,回忆插入排序,当拿到一张新的扑克牌,我们需要拿着它逐一与手中的牌比较。当这张新的扑克牌恰好是最小的,那意味着手里有多少张牌就要移动多少次,所以插入排序的时间复杂度跟原数组的有序程度紧密相连。

为了提高插入排序的效率,算法专家考虑是否能先把数组变得相对有序一些,尽量先把数组中较大的和较小的分别放置在数组的末尾和开头,这样比较的次数就会下降很多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Python program for implementation of Shell Sort 

def shellSort(arr):

n = len(arr)
gap = n // 2 # 初始化间隔,间隔的取舍没有确切的规定

while gap > 0:

for i in range(gap, n): # 索引从间隔(gap)-->数组的末尾(n)

new_card = arr[i] # 手中的扑克牌

j = i - gap # 索引间隔gap左侧的元素
while j >= 0 and arr[j] > new_card: # 当左侧的元素大于手中的扑克牌
arr[j + gap] = arr[j] # 将较大的元素放在i=j+gap的位置
j -= gap

arr[j + gap] = new_card # gap左侧的元素遍历完了,将手中的扑克牌放在j+gap的位置,同插入排序
gap //= 2

对比插入排序,其实代码的差别不大,只不过把代码中的1换成了gap:

1
2
3
4
5
6
7
8
9
def insert_sort(array):
for i in range(1, len(array)):
new_card = array[i] # 手中的牌
j = i - 1
while j >= 0 and new_card < array[j]: # 新摸到的牌如果大于手中的牌则往后移动
array[j+1] = array[j]
j -= 1
array[j+1] = new_card
return array
觉得还不错?赞助一下~
0%