不为成仙,只为在这红尘中等你回来。

您现在的位置是:网站首页>>算法与数据结构

希尔排序

2020年11月6日 22:15 | 分类:算法与数据结构 | 标签: Python

  • 希尔排序(shell sort)是一种分组插入排序算法。
  • 首先取一个整数 d₁ = n // 2,将元素分为 d₁ 个组,每组相邻元素之间距离为 d₁,在各组内进行直接插入排序;
  • 取第二个整数 d₂ = d₁ // 2,重复上述分组排序过程,直到 dᵢ = 1,即所有元素在同一组内进行直接插入排序。
  • 希尔排序每趟并不使某些元素有序,而是使整体数据越来越接近有序,最后一趟排序使得所有数据有序。

希尔排序

# 希尔排序
def insert_sort_gap(lst, gap):
    for i in range(gap, len(lst)):
        tmp = lst[i]
        j = i - gap
        while j >= 0 and lst[j] > tmp:
            lst[j + gap] = lst[j]
            j -= gap
        lst[j + gap] = tmp


def shell_sort(lst):
    d = len(lst) // 2
    while d >= 1:
        insert_sort_gap(lst, d)
        d //= 2

import random

lst = list(range(1000))
random.shuffle(lst)
shell_sort(lst)
print(lst)

注:希尔排序的时间复杂度比较复杂,并且和选取的 gap 序列有关。