一、原理
-
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])
运行结果如下，)
：
