vlambda博客
学习文章列表

简单插入排序&希尔排序(python)


我不爱机器学习
专注机器学习、数据分析、编程语言,欢迎交流学习
129篇原创内容
Official Account


简单插入排序

基本思想:

  • 当前元素与前一个元素比较,若前一个元素大于当前元素,则前一个元素后移,并用指针记录此时的位置;
  • 重复此过程,直到找到比其小的元素,则将元素赋给此时指针指向的位置;重复上面两个过程,直到当前元素为最后一个元素;
  • 注意,当前元素是从前往后开始取,但比较时,是从当前位置向前比较,并用指针记录位置,此时当前元素的前面元素均已排序。
def insertSort(lst):
    n = len(lst)
    if n <= 1return lst

    # 遍历所有的元素
    for i in range(1, n):
        cur = lst[i]  # 当前元素
        j = i - 1  # 位置记录指针

        # 当前元素小于前一个元素
        while j >= 0 and cur < lst[j]:
            lst[j + 1] = lst[j]  # 前一个元素往后移
            j -= 1

        # 此时的j指向前一个元素(前一个元素<=cur)
        lst[j + 1] = cur
    return lst


lst = input('输入数字:').split(' ')
lst = [eval(x) for x in lst]
insertSort(lst)

希尔排序

基本思想:

  • 对不同间隔的元素进行比较,从后向前比较;
  • 间隔取值为 np.arange(n//2,0,-1),从大到小进行取值;
  • 如[3,4,5,2,1],间隔为2时,5,3比较,2,4比较,1,5比较,1,3比较;间隔为1时,4,3比较,5,4比较,5,3比较......;
  • 是一个递归过程。
def shellSort(lst):
    # start with a big gap,then reduce the gap
    n = len(lst)
    gap = n // 2

    print(lst)

    # Do a gapped insertion sort for this gap size.
    # The first gap elements lst[0..gap-1] are already in gapped
    # order keep adding one more element until the entire array
    # is gap sorted
    while gap > 0:
        for i in range(gap, n):
            # save lst[i] in cur and make a hole at position i
            cur = lst[i]  # 获取当前元素,因为是从后往前比较,因此从gap开始

            j = i  # 位置记录指针
            while j >= gap and lst[j - gap] > cur:
                lst[j] = lst[j - gap]
                j -= gap

            # put cur (the lst[i]) in its correct location
            lst[j] = cur
            print(lst)

        gap = gap // 2
    return lst


# -------------------------------------------------------------
# 递归写法
def shellSort(lst):
    def sort(lst, gap):
        for i in range(gap, n):
            cur = lst[i]  # 获取当前元素,因为是从后往前比较,因此从gap开始

            j = i  # 位置记录指针
            while j >= gap and lst[j - gap] > cur:
                lst[j] = lst[j - gap]
                j -= gap

            lst[j] = cur

    n = len(lst)
    gap = n // 2
    while gap > 0:
        sort(lst, gap)
        gap = gap // 2
    return lst


lst = input('输入数字:').split(' ')
lst = [eval(x) for x in lst]
shellSort(lst)


总结:都是从前往后遍历,再从后往前比较。