插入排序：直接插入排序和希尔排序

一、原理

• 1.直接插入排序(Straight Insertion Sort)

  
  • 1.先将数组arr分为左右两部分，左侧为已排序的列表sorted_list=[arr[0]]，右侧为未排序的列表unsorted_list=arr[1:]。
  • 2.依次遍历unsorted_list列表中的元素a：
    • 元素a与sorted_list中的元素b从后向前依次进行比较；
    • 满足条件a<b或a>b(根据排序顺序确定)时，b元素往后移动一格；
    • 直到最终不满足条件时，将元素a填入sorted_list中的索引空位。

• 2.希尔排序(Shell's Sort)

  
  • 希尔排序是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。一般的初次取序列的一半为增量，以后每次减半，直到增量为1(增量为何这样取？是为了减少平均时间复杂度。这种取法对大部分的数组来说是高效的，但不能说一定是最优解)。
  • 1.取序列长度的一半(向下取整)作为增量gap，对序列进行分组，然后对各组进行“直接插入排序”。
  • 2.增量gap依次减半(向下取整)，重复上面的分组排序操作，最终一个的增量gap为1。

• 3.问题：希尔排序是先分组，再用“直接插入排序”，当增量减至1时，是对所有数据执行“直接插入排序”。那么，为什么不一开始就直接对所有数据执行“直接插入排序”呢？希尔排序是直接插入排序的高效改进版，希尔排序这样做，它的高效体现在哪？

  • 首先，“直接插入排序”有一个比较提前终止的性质，因此，对于近乎有序的数组，它的排序速度很快。
  • 然而，对于大部分较小值位于末端的数组，“直接插入排序”需要逐个往前比较和交换，是非常低效的。
  • 针对“直接插入排序”的这个弊端，提出了希尔排序。希尔排序通过分组的形式，可直接将末端元素与前段元素进行比较和交换，从而减少比较和交换次数，提高效率。特别地，当组数长度越大、数组越无序时，性能提升越明显。

二、代码实现

题目：随机给定一个数组，按从小到大排序。

逻辑代码：

from time import time
import numpy as np


# 直接插入排序
def straight_insertion_sort(arr):
    # 依次遍历unsorted_list列表中的元素，索引位置从1开始
    for i in range(1, len(arr)):
        value = arr[i]  # 获取a元素
        index = i - 1  # sorted_list列表中最后一个元素b的索引位置

        # 将a元素依次与sorted_list中的元素b从后向前比较
        # 目的：将a元素插入sorted_list列表中的正确排序位置上
        while index >= 0 and arr[index] > value:
            arr[index + 1] = arr[index]  # 满足条件，sorted_list中的b元素右移一格
            index -= 1
        arr[index + 1] = value  # 元素a填入sorted_list中的索引空位


# 希尔排序
def shell_sort(arr):
    n = len(arr)
    gap = int(n / 2)
    while gap > 0:
        # 按gap分组，并对每组进行“直接插入排序”操作
        for i in range(gap, n):
            value = arr[i]
            index = i - gap
            while index >= 0 and arr[index] > value:
                arr[index + gap] = arr[index]
                index -= gap
            arr[index + gap] = value

        # 增量gap减半
        gap = int(gap / 2)


if __name__ == "__main__":
    # 直接插入排序
    np.random.seed(10)
    array = list(np.random.randint(0, 1000, size=(2000,)))
    start = time()
    straight_insertion_sort(array)
    end = time()
    print(f"straight_insertion_sort()函数耗时{end - start}秒")
    print(array[:100])

    # 希尔排序
    np.random.seed(10)
    array = list(np.random.randint(0, 1000, size=(2000,)))
    start = time()
    shell_sort(array)
    end = time()
    print(f"shell_sort()函数耗时{end - start}秒")
    print(array[:100])

运行结果如下，：