【数据结构常见七大排序（一）】—插入排序篇【直接插入排序】And【希尔排序】

**数据结构常见七大排序（一）**

在计算机科学中，排序是指将一个无序的集合中的元素按照某种规则重新排列，使得集合中的每个元素都有一个确定的位置。排序算法是实现这一功能的关键步骤。在本文中，我们将介绍数据结构常见七大排序中的两种：直接插入排序和希尔排序。

**一、直接插入排序**

直接插入排序是一种简单而有效的排序算法，它通过对每个元素进行比较并交换来实现排序。具体来说，直接插入排序从第一个元素开始，对其后面的所有元素进行比较，并将较大的元素向右移动，以便新元素可以插入到正确的位置。

**算法步骤：**

1. 从第一个元素开始，对其后面的所有元素进行比较。
2. 如果当前元素小于或等于前面一个元素，则不需要交换。
3. 如果当前元素大于前面一个元素，则将前面一个元素向右移动一位，直到找到正确的插入位置。

**代码示例：**

def direct_insert_sort(arr):
 n = len(arr)
 for i in range(1, n):
 key = arr[i]
 j = i -1 # 将较大的元素向右移动 while j >=0 and arr[j] > key:
 arr[j +1] = arr[j]
 j -=1 # 插入新元素 arr[j +1] = key return arr# 测试代码arr = [5,2,8,3,1,6,4]
print("原始数组：", arr)
print("排序后数组：", direct_insert_sort(arr))

**二、希尔排序**

希尔排序是一种改进的插入排序算法，它通过分割待排序序列为几个小序列，然后对每个小序列进行直接插入排序来实现排序。具体来说，希尔排序首先将整个序列分成多个小组，每个小组中的元素都有一个确定的位置，然后再对每个小组中的元素进行直接插入排序。

**算法步骤：**

1. 将整个序列分成多个小组，每个小组中的元素都有一个确定的位置。
2. 对每个小组中的元素进行直接插入排序。
3. 合并所有的小组，得到最终的排序结果。

**代码示例：**

def shell_sort(arr):
 n = len(arr)
 # 初始化增量序列 gap = n //2 while gap >0:
 for i in range(gap, n):
 key = arr[i]
 j = i - gap # 将较大的元素向右移动 while j >=0 and arr[j] > key:
 arr[j + gap] = arr[j]
 j -= gap # 插入新元素 arr[j + gap] = key # 缩小增量 gap //=2 return arr# 测试代码arr = [5,2,8,3,1,6,4]
print("原始数组：", arr)
print("排序后数组：", shell_sort(arr))

**总结**

在本文中，我们介绍了数据结构常见七大排序中的两种：直接插入排序和希尔排序。直接插入排序是一种简单而有效的排序算法，它通过对每个元素进行比较并交换来实现排序。希尔排序是一种改进的插入排序算法，它通过分割待排序序列为几个小序列，然后对每个小序列进行直接插入排序来实现排序。两种算法都有其特点和应用场景，选择哪种算法取决于具体的需求和性能要求。