python实现插入排序&希尔排序

为什么要将插入排序和希尔排序放在一起来写呢？因为插入排序和希尔排序的思路是相同的，希尔排序可以看成是插入排序的特殊情况，下面就来详细说说两者的思路。

---

1. 插入排序

插入排序原理：每次将无序序列中的首个元素在已排序序列中从后向前扫描，按照给定规律找到相应位置并插入。在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。

1.1 第一次排序

假设下面存在一组无序数列[9,7,3,3,6,2,1,4,10]，需要通过插入排序将其变为[1,2,3,3,4,6,7,9,10]。
先通过插入排序分析第一次排序是怎么个过程。

• 分为左右两部分，左边为0号索引位置元素9【假设为有序序列】，右边为(1,n-1)索引位置的元素【假设为无序序列】，每次都拿右边首个元素与左边的元素进行对比【第一次排序下为1索引位置元素】，按照规律插入到左边有序序列对应位置中。
• 有序序列部分元素为9，无序序列部分首元素为7，7比9小，所以交换彼此的位置，将7插入到9前面，则7和9的序列就已经确定。第一轮排序结束后，有序序列部分元素有7、9，无序序列部分从索引2开始到n-1

• 根据以上原理和图解，可以完成以下代码

"""第一次插入排序"""
def insert_sort(target_list):
    i = 1  # 右边无序序列的首个元素索引
    # 后面元素比前面元素小，交换两个元素位置
    if target_list[i] < target_list[i-1]:
        target_list[i],target_list[i-1] = target_list[i-1],target_list[i]

1.2 第二次排序

• 右边无序部分首个元素【此时为2索引位置元素3】，依次与左边有序部分每个元素进行对比，如果比左边的元素小，则交换彼此的位置
• 3先跟9对比，比9小，则交换彼此位置【此时左边是7 3 9】，再跟7对比，比7小，交换彼此位置【此时是 3 7 9】
• 假设3所对应的游标是i，可以看出i不断的往前移动，即每次比较i都要往左移动一个单位【i -= 1】

1.3 第n次排序

• 由于需要对 右边无序列表的每一个元素都与左边进行对比，起使时默认0号元素为有序列表，因此无序列表的索引位置为(1,n-1)，用j表示每次循环时右边无序列表首位的索引位置，而range()函数左闭右开，因此代码为for j in range(1,n)
• 由于i游标每次都需要往左移动一个单位，不断与前一个元素对比，直到插入到正确的位置，因此移动条件为while i >0,当target_list[i]比前target_list[i-1]大的时候停止移动

def insert_sort(alist):
    """插入算法"""
    n = len(alist)
    # 从右边的无序序列中取出多少个元素执行这样的过程
    for j in range(1,n):
        i = j
        # 循环条件为i>0,因为需要与左边有序列表的每个元素进行比较，一直移动到0号索引位置
        while i>0:
            if alist[i] < alist[i-1]:
                alist[i],alist[i-1] = alist[i-1],alist[i]
                i -= 1
            else:
                # 如果alist[i]位置的元素比alist[i-1]大，说明已经到了指定位置，则退出循环
                break

2. 希尔排序

• 希尔排序可以看成插入排序的改进版，原理与插入排序类似
• 将数组视为很多个无序的序列，先确定一个间隔gap，以gap为单位，每个元素与其索引+gap位置的元素组成一个序列，使用插入算法的思想进行排序
• 缩小gap的值，重复上述步骤
• 当gap缩小到1时，即为插入排序
  
  

2.1 第一次排序

排序思路图
第一次排序完成图

• 假设gap取值为n/2,则可将上述数组分为如上图所示4组无序数列，对每组无序数列都使用插入算法后，数组的顺序变为[6 2 1 3 9 7 3 4 10]

• gap减少为原gap值得一半 即 gap //= 2

• 每一个使用gap分离后得数组，按照插入排序得思想，其右边无序列表得第一个元素所对应得索引位置为gap

2.2 第二次排序

• 经过第一次排序后，数组元素顺序变为[6,2,1,3,9,7,3,4,10]
• gap缩小为2

• 实现变化后的数组和缩小后的gap重复第一步步骤

  
  第二次排序思路图
  第二次排序完成图

2.3 第n次排序

• 第二次排序完成后，数组变为 1 2 3 4 6 4 9 7 10
• gap继续缩小为原来得一半，然后执行下一次排序
• 直到gap=1时，为最后一次排序，此时相当于插入排序
• 代码实现【只需要将插入排序得步长和无序列表起始位置改为gap；添加gap长度变化的规则即可】

def shell_sort(target_list):
    n = len(target_list)
    gap = n // 2
    # 当gap>=1时循环进行
    while gap >= 1:
        # j 代表右边无序列表得起始位置
        for j in range(gap,n):
            i = j
            while i > 0:
                if target_list[i] < target_list[i-gap]:
                    target_list[i],target_list[i-gap] = target_list[i-gap],target_list[i]
                else:
                    break
        # 每次gap缩小为原来得一半
        gap //= 2