vlambda博客
学习文章列表

简单插入排序

基本思想：

• 当前元素与前一个元素比较，若前一个元素大于当前元素，则前一个元素后移，并用指针记录此时的位置；
• 重复此过程，直到找到比其小的元素，则将元素赋给此时指针指向的位置；重复上面两个过程，直到当前元素为最后一个元素；
• 注意，当前元素是从前往后开始取，但比较时，是从当前位置向前比较，并用指针记录位置，此时当前元素的前面元素均已排序。

def insertSort(lst):
    n = len(lst)
    if n <= 1: return 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)