1冒泡排序：
冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
代码如下：
import numpy as np
def bubbling(arr):
n = len(arr)
for i in range(n-1):
for j in range(n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
old_list = np.random.randint(100,size=6)
print(f"未排序的列表{old_list}")
new_list = bubbling(old_list)
print(f"排完序后的列表{[int(x) for x in new_list]}")代码详解：
-
bubbling函数：- 首先获取输入数组的长度
n。 - 外层循环
for i in range(n - 1)控制排序的轮数。每一轮都会将当前未排序部分中的最大元素 “冒泡” 到末尾。 - 内层循环
for j in range(n - i - 1)遍历未排序部分的元素，进行相邻元素的比较和交换。如果当前元素大于下一个元素，就交换它们的位置。 - 最终返回排序后的数组。
- 首先获取输入数组的长度
下面是举实例：
假设有一个随机生成的numpy数组old_list = [45, 78, 22, 63, 30, 85]。
-
bubbling函数：n = len(arr)：这里n = 6，即数组的长度。- 外层循环
for i in range(n - 1)：- 第一轮（
i = 0）：- 内层循环
for j in range(n - i - 1)，此时相当于for j in range(5)。- 第一次比较：
j = 0，比较arr[0]（45）和arr[1]（78），因为 45 不大于 78，所以不交换。 - 第二次比较：
j = 1，比较arr[1]（78）和arr[2]（22），因为 78 大于 22，所以交换这两个元素，数组变为[45, 22, 78, 63, 30, 85]。 - 继续进行比较和交换操作，直到本轮结束。此时，本轮最大的元素 78 被 “冒泡” 到了当前未排序部分的末尾。
- 第一次比较：
- 内层循环
- 第二轮（
i = 1）：- 内层循环范围变为
for j in range(4)。重复类似的比较和交换操作，将第二大的元素放到合适的位置。
- 内层循环范围变为
- 以此类推，经过多轮循环，最终将数组排序。
- 第一轮（
2插入排序：
插入排序是一种简单的排序算法，它将未排序的数据逐一插入到已排序的部分中，最终使整个数组有序。
代码如下：
import numpy as np
def insert(arr):
n = len(arr)
for i in range(1,n):
j = i
while arr[j] < arr[j-1] and j >=1 :
arr[j], arr[j-1] = arr[j-1], arr[j]
j -= 1
return arr
old_list = np.random.randint(100,size=6)
print(f"未排序的列表{old_list}")
new_list = insert(old_list)
print(f"排完序后的列表{[int(x) for x in new_list]}")代码详解：
-
insert函数：n = len(arr)：获取输入数组的长度。for i in range(1, n)：从第二个元素开始遍历数组，因为第一个元素可以认为是已排序的部分。j = i：设置一个指针j，初始值为当前要插入的元素的索引。while arr[j] < arr[j - 1] and j >= 1：当当前元素小于前一个元素且索引大于等于 1 时，进行循环。这意味着只要当前元素在合适的位置之前，就不断地将其与前一个元素交换位置，以将其插入到已排序部分的正确位置。arr[j], arr[j - 1] = arr[j - 1], arr[j]：交换当前元素和前一个元素的位置。j -= 1：将指针向前移动一位，继续比较和交换，直到找到合适的位置插入当前元素。
下面是举实例：
假设我们有一个随机生成的numpy数组old_list = [45, 78, 22, 63, 30, 85]
-
insert函数：n = len(arr)：这里n = 6，即数组的长度。for i in range(1, n)：从第二个元素开始遍历数组。- 第一轮（
i = 1）：j = i，此时j = 1。比较arr[j]（78）和arr[j - 1]（45），因为 78 不小于 45，所以不进入循环，数组保持不变。
- 第二轮（
i = 2）：j = i，此时j = 2。比较arr[j]（22）和arr[j - 1]（78），因为 22 小于 78，进入循环。arr[j], arr[j - 1] = arr[j - 1], arr[j]，交换这两个元素，数组变为[45, 22, 78, 63, 30, 85]。j -= 1，此时j = 1。继续比较arr[j]（22）和arr[j - 1]（45），因为 22 小于 45，再次交换，数组变为[22, 45, 78, 63, 30, 85]。
- 第三轮（
i = 3）：- 类似地进行比较和交换操作，将合适的元素插入到已排序部分。
- 以此类推，直到整个数组有序。
- 第一轮（
3选择排序：
选择排序是一种简单的排序算法，它每次从未排序的部分中找到最小的元素，然后将其与未排序部分的第一个元素交换位置，逐步将整个数组排序。
代码如下：
import numpy as np
def select(arr):
n = len(arr)
for i in range(n-1):
min_val1 = i
for j in range(i+1,n):
if arr[j] < arr[min_val1]:
min_val1= j
arr[i], arr[min_val1] = arr[min_val1], arr[i]
return arr
old_list = np.random.randint(100,size=6)
print(f"未排序的列表{old_list}")
new_list = select(old_list)
print(f"排完序后的列表{[int(x) for x in new_list]}")代码详解：
-
select函数：n = len(arr)：获取输入数组的长度。for i in range(n - 1)：外层循环控制已排序部分的边界。从第一个元素开始，逐步将最小的元素放到已排序部分的末尾。min_val1 = i：初始化当前最小元素的索引为i。for j in range(i + 1, n)：内层循环遍历未排序部分的元素，找到最小的元素。if arr[j] < arr[min_val1]：如果当前元素小于当前认为的最小元素，则更新最小元素的索引。arr[i], arr[min_val1] = arr[min_val1], arr[i]：将找到的最小元素与未排序部分的第一个元素交换位置。
下面是举实例：
假设我们有一个随机生成的numpy数组old_list = [45, 78, 22, 63, 30, 85]。
-
select函数：n = len(arr)：这里n = 6，即数组的长度。- 第一轮（
i = 0）：min_val1 = i，此时min_val1 = 0，假设当前最小元素的索引为第一个元素的索引。for j in range(i + 1, n)，即for j in range(1, 6)。- 第一次比较：
j = 1，比较arr[1]（78）和arr[0]（45），因为 78 不小于 45，所以不更新最小元素索引。 - 继续比较，当
j = 2时，发现arr[2]（22）小于当前认为的最小元素arr[0]（45），更新min_val1 = 2。 - 继续遍历完未排序部分，确定当前最小元素的索引为 2。
- 第一次比较：
arr[i], arr[min_val1] = arr[min_val1], arr[i]，交换arr[0]和arr[2]，数组变为[22, 78, 45, 63, 30, 85]。
- 第二轮（
i = 1）：- 重复上述过程，在未排序部分（
arr[1]到arr[5]）中找到最小元素，并与未排序部分的第一个元素交换位置。
- 重复上述过程，在未排序部分（
- 以此类推，直到整个数组有序。
4快速排序
快速排序是一种高效的排序算法，它通过选择一个基准元素，将数组分为小于基准元素、等于基准元素和大于基准元素的三个部分，然后对这三个部分分别进行递归排序，最终得到一个有序的数组。
代码如下：
import numpy as np
def quick(arr):
n = len(arr)
if n <= 1 :
return arr
mid = arr[n//2]
left = [x for x in arr if x < mid]
middle = [x for x in arr if x== mid]
right = [x for x in arr if x > mid]
return quick(left) + middle + quick(right)
old_list = np.random.randint(100,size=6)
print(f"未排序的列表{old_list}")
new_list = quick(old_list)
print(f"排完序后的列表{[int(x) for x in new_list]}")代码详解：
-
quick函数：n = len(arr)：获取输入数组的长度。if n <= 1:：如果数组长度小于等于 1，则直接返回该数组，因为一个元素或空数组本身就是有序的。mid = arr[n // 2]：选择数组的中间元素作为基准元素。left = [x for x in arr if x < mid]：使用列表推导式创建一个新的列表，包含所有小于基准元素的元素。middle = [x for x in arr if x == mid]：创建一个列表，包含所有等于基准元素的元素。right = [x for x in arr if x > mid]：创建一个列表，包含所有大于基准元素的元素。return quick(left) + middle + quick(right)：对小于基准元素的部分和大于基准元素的部分分别进行递归排序，然后将三个部分合并起来返回。
下面是举实例：
假设我们有一个随机生成的numpy数组old_list = [45, 78, 22, 63, 30, 85]
-
quick函数：-
n = len(arr)：这里n = 6，即数组的长度。 -
if n <= 1:：如果数组长度小于等于 1，则直接返回该数组。 -
mid = arr[n // 2]：选择数组的中间元素作为基准元素，这里mid = arr[3] = 63。 -
left = [x for x in arr if x < mid]：创建一个新的列表，包含所有小于基准元素的元素，即left = [45, 22, 30]。 -
middle = [x for x in arr if x == mid]：创建一个列表，包含所有等于基准元素的元素，即middle = [63]。 -
right = [x for x in arr if x > mid]：创建一个列表，包含所有大于基准元素的元素，即right = [78, 85]。 -
return quick(left) + middle + quick(right)：对小于基准元素的部分和大于基准元素的部分分别进行递归排序，然后将三个部分合并起来返回。 -
对于
left部分[45, 22, 30]，再次进行快速排序：- 选择中间元素
30作为新的基准元素。 - 得到
left = [22]，middle = [30]，right = [45]。 - 继续递归排序，直到子数组长度小于等于 1。
- 选择中间元素
-
对于
right部分[78, 85]，选择中间元素85作为基准元素，得到left = []，middle = [85]，right = [78]。 -
最后将排序后的子数组合并起来，得到
[22, 30, 45] + [63] + [78, 85] = [22, 30, 45, 63, 78, 85]。
-
5归并排序：
归并排序是一种分治算法，它将一个数组不断地分成两部分，分别对两部分进行排序，然后再将两个已排序的子数组合并成一个有序的数组。
代码如下：
import numpy as np
def merge_sort(arr):
n = len(arr)
if n <= 1:
return arr
mid = n//2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j =0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
if i < len(left):
result.extend(left[i:])
if j < len(right):
result.extend(right[j:])
return result
old_list = np.random.randint(100,size=6)
print(f"未排序的列表{old_list}")
new_list = merge_sort(old_list)
print(f"排完序后的列表{[int(x) for x in new_list]}")代码详解：
-
merge_sort函数：n = len(arr)：获取输入数组的长度。if n <= 1:：如果数组长度小于等于 1，则直接返回该数组，因为一个元素或空数组本身就是有序的。mid = n//2：计算数组的中间位置。left = merge_sort(arr[:mid])：对数组的左半部分进行递归排序。right = merge_sort(arr[mid:])：对数组的右半部分进行递归排序。return merge(left, right)：调用merge函数将两个已排序的子数组合并成一个有序的数组并返回。
-
merge函数：result = []：创建一个空列表用于存储合并后的结果。i = j = 0：初始化两个指针，分别指向左子数组和右子数组的开头。while i < len(left) and j < len(right)：当两个子数组都还有元素时，进行循环。if left[i] < right[j]：如果左子数组当前元素小于右子数组当前元素，则将左子数组当前元素添加到结果列表中，并将左指针向后移动一位。- 否则，将右子数组当前元素添加到结果列表中，并将右指针向后移动一位。
if i < len(left)：如果左子数组还有剩余元素，将其全部添加到结果列表中。if j < len(right)：如果右子数组还有剩余元素，将其全部添加到结果列表中。return result：返回合并后的结果列表。
下面是举例：
假设我们有一个随机生成的numpy数组old_list = [45, 78, 22, 63, 30, 85]
-
merge_sort函数：n = len(arr)：这里n = 6，即数组的长度。if n <= 1:：如果数组长度小于等于 1，则直接返回该数组。mid = n//2：计算中间位置，这里mid = 3。left = merge_sort(arr[:mid])：对左半部分[45, 78, 22]进行递归排序。- 再次进入
merge_sort函数，对[45, 78]进行分割和排序。- 继续分割为
[45]和[78]，因为长度为 1，直接返回。 - 调用
merge函数合并[45]和[78]，得到[45, 78]。
- 继续分割为
- 对
[22]直接返回。 - 再次调用
merge函数合并[45, 78]和[22]，得到[22, 45, 78]。
- 再次进入
right = merge_sort(arr[mid:])：对右半部分[63, 30, 85]进行递归排序。- 类似地进行分割和排序，最终得到
[30, 63, 85]。
- 类似地进行分割和排序，最终得到
return merge(left, right)：调用merge函数将左半部分和右半部分合并。
-
merge函数：-
result = []：创建一个空列表用于存储合并后的结果。 -
i = j = 0：初始化两个指针，分别指向左子数组和右子数组的开头。 -
while i < len(left) and j < len(right)：当两个子数组都还有元素时，进行循环。- 比较左子数组和右子数组的当前元素，将较小的元素添加到结果列表中，并移动相应的指针。
-
if i < len(left)：如果左子数组还有剩余元素，将其全部添加到结果列表中。 -
if j < len(right)：如果右子数组还有剩余元素，将其全部添加到结果列表中。 -
return result：返回合并后的结果列表。 -
对于上面的例子，合并
[22, 45, 78]和[30, 63, 85]，首先比较22和30，将22添加到结果列表中，然后比较45和30，将30添加到结果列表中，以此类推，最终得到[22, 30, 45, 63, 78, 85]。
-
6堆排序
堆排序是一种利用堆这种数据结构进行排序的算法，它分为两个主要阶段：构建最大堆和进行排序。
代码如下：
import numpy as np
def heapify(arr,n,i):
largest = i
left = 2*i + 1
right = 2*i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largerst = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr,n,largest)
def heap(arr):
n = len(arr)
for i in range(n//2 , -1,-1):
heapify(arr,n,i)
for i in range(n-1,0,-1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr,i,0)
return arr
old_list = np.random.randint(100,size=6)
print(f"未排序的列表{old_list}")
new_list = heap(old_list)
print(f"排完序后的列表{[int(x) for x in new_list]}")代码详解：
-
heapify函数：- 这个函数用于维护最大堆的性质。它接受一个数组
arr、数组长度n和一个索引i。 largest = i首先假设当前索引i对应的元素是最大的。left = 2*i + 1和right = 2*i + 2计算当前节点的左子节点和右子节点的索引。- 如果左子节点存在且大于当前最大元素，更新
largest为左子节点的索引。 - 如果右子节点存在且大于当前最大元素，更新
largest为右子节点的索引。 - 如果
largest不等于i，说明需要调整堆，交换arr[i]和arr[largest]，然后递归地调用heapify函数对新的largest位置进行调整。
- 这个函数用于维护最大堆的性质。它接受一个数组
-
heap函数：n = len(arr)获取数组的长度。- 第一个循环用于构建最大堆。从最后一个非叶子节点
n//2 - 1开始，逐步向前遍历，对每个节点调用heapify函数来确保最大堆的性质。 - 第二个循环用于进行排序。从最后一个元素开始，每次将堆顶元素（当前最大元素）与最后一个未排序的元素交换，然后对新的堆顶元素调用
heapify函数，缩小堆的范围，继续进行下一次交换和调整，直到整个数组有序。
下面是举例：
假设我们有一个随机生成的数组old_list = [33, 55, 11, 44, 22, 66]
-
构建最大堆过程：
- 首先计算非叶子节点的索引。这里有 6 个元素，非叶子节点是索引为 0、1、2 的元素。
- 处理索引为 2 的元素，即数字 11。它的左子节点是 5（索引为 5 的元素 66），右子节点不存在。因为 66 大于 11，所以交换这两个元素，得到
[33, 55, 66, 44, 22, 11]。 - 接着处理索引为 1 的元素，即数字 55。它的左子节点是 3（索引为 3 的元素 44），右子节点是 4（索引为 4 的元素 22）。比较后无需调整。
- 最后处理索引为 0 的元素，即数字 33。它的左子节点是 1（索引为 1 的元素 55），右子节点是 2（索引为 2 的元素 66）。比较后发现最大元素是 66，交换
arr[0]和arr[2]，得到[66, 55, 33, 44, 22, 11]。此时最大堆构建完成。
-
进行排序过程：
- 交换堆顶元素和最后一个未排序的元素，即交换
arr[0]和arr[5]，得到[11, 55, 33, 44, 22, 66]，然后对新的堆顶元素调用heapify函数，此时堆的大小为 5。 - 继续交换堆顶元素和当前最后一个未排序的元素，重复这个过程。
- 第二次交换后得到
[22, 55, 33, 44, 11, 66]，对新的堆顶调用heapify，堆的大小为 4。 - 第三次交换后得到
[33, 55, 22, 44, 11, 66]，对新的堆顶调用heapify，堆的大小为 3。 - 第四次交换后得到
[44, 55, 22, 33, 11, 66]，对新的堆顶调用heapify，堆的大小为 2。 - 第五次交换后得到
[55, 44, 22, 33, 11, 66]，对新的堆顶调用heapify，堆的大小为 1。 - 最终得到排完序后的列表
[11, 22, 33, 44, 55, 66]。
- 交换堆顶元素和最后一个未排序的元素，即交换
7计数排序
计数排序是一种非比较型整数排序算法，它通过统计每个元素在序列中出现的次数，然后根据出现次数确定每个元素在排序后的序列中的位置。
代码如下：
import numpy as np
def count(arr):
if len(arr) == 0:
return arr
min_val1 = min(arr)
max_val1 = max(arr)
range_val1 = max_val1 - min_val1 + 1
count_list = [0] * range_val1
output_list = [0] * len(arr)
for num in arr:
count_list[num - min_val1] += 1
for i in range(1,len(count_list)):
count_list[i] += count_list[i - 1]
for num in reversed(arr):
index = count_list[num - min_val1] - 1
output_list[index] = num
count_list[num - min_val1] -= 1
return output_list
old_list = np.random.randint(100,size=6)
print(f"未排序的列表{old_list}")
new_list = count(old_list)
print(f"排完序后的列表{[int(x) for x in new_list]}")代码详解：
-
count函数：if len(arr) == 0:：如果输入数组为空，则直接返回空数组。min_val1 = min(arr)和max_val1 = max(arr)：找到输入数组中的最小值和最大值。range_val1 = max_val1 - min_val1 + 1：计算数据的取值范围。count_list = [0] * range_val1：创建一个计数列表，用于统计每个值出现的次数。output_list = [0] * len(arr)：创建一个输出列表，用于存储排序后的结果。- 第一个循环遍历输入数组，将每个元素的值减去最小值作为计数列表的索引，将对应位置的计数加一。
- 第二个循环对计数列表进行累加操作，使得计数列表中的每个位置的值表示小于或等于该位置索引对应的元素在输出数组中的最终位置。
- 第三个循环逆序遍历输入数组，根据每个元素在计数列表中的位置信息，将其放置在输出数组的正确位置，并更新计数列表中的值。
-
主程序部分：
old_list = np.random.randint(100, size = 6)：生成一个包含 6 个随机整数（范围在 0 到 99 之间）的numpy数组。print(f"未排序的列表{old_list}")：打印未排序的列表。new_list = count(old_list)：调用count函数对old_list进行排序。print(f"排完序后的列表{[int(x) for x in new_list]}")：打印排完序后的列表，使用列表推导式将numpy数组中的元素转换为整数类型后输出。
下面是举例：
假设我们有一个随机生成的数组old_list = [37, 52, 28, 46, 33, 60]
-
确定最小值和最大值：
min_val1 = min(arr)，在这个例子中，min_val1 = 28。max_val1 = max(arr)，这里max_val1 = 60。
-
计算取值范围：
range_val1 = max_val1 - min_val1 + 1，即60 - 28 + 1 = 33。
-
创建计数列表和输出列表：
count_list = [0] * range_val1，创建一个长度为 33 的计数列表，初始值都为 0。output_list = [0] * len(arr)，创建一个长度为 6 的输出列表，初始值也为 0。
-
统计每个元素出现的次数：
- 遍历输入数组，对于元素 37，在计数列表中的索引为
37 - 28 = 9，将count_list[9]的值加一。 - 继续遍历，对于元素 52，索引为
52 - 28 = 24，将count_list[24]的值加一。 - 以此类推，遍历完整个输入数组后，计数列表反映了每个值在输入数组中出现的次数。
- 遍历输入数组，对于元素 37，在计数列表中的索引为
-
累加计数列表：
- 初始时，
count_list[0]保持不变。 count_list[1] = count_list[1] + count_list[0]。- 继续进行累加操作，这样，计数列表中的每个位置的值表示小于或等于该位置索引对应的元素在输出数组中的最终位置。
- 初始时，
-
确定输出列表中的元素位置：
- 逆序遍历输入数组，对于元素 60，在计数列表中的索引为
60 - 28 = 32，此时count_list[32]的值表示元素 60 在输出列表中的位置索引。将 60 放置在输出列表的这个位置，并将count_list[32]的值减一。 - 对于下一个元素继续这个过程，直到遍历完整个输入数组。
- 逆序遍历输入数组，对于元素 60，在计数列表中的索引为
最终，输出列表就是排完序后的列表，即[28, 33, 37, 46, 52, 60]。
8基数排序
基数排序是一种非比较型整数排序算法，它通过对数字的各个位进行分别排序来实现对整个数组的排序。
代码如下：
import numpy as np
def redix(arr):
max_num = max(arr)
div = 1
while max_num // div > 0:
bucket = [[] for _ in range(10)]
for num in arr:
digit = (num //div) % 10
bucket[digit].append(num)
arr = [x for x in bucket for x in x]
div *=10
return arr
old_list = np.random.randint(100,size=6)
print(f"未排序的列表{old_list}")
new_list = redix(old_list)
print(f"排完序后的列表{[int(x) for x in new_list]}")代码详解：
-
redix函数：max_num = max(arr)：找到输入数组中的最大数。div = 1：初始化用于确定当前要排序的位数的除数。while max_num // div > 0：当最大数除以当前除数大于 0 时，说明还有位数需要排序。bucket = [[] for _ in range(10)]：创建 10 个空桶，用于存储不同位数的值。for num in arr:：遍历输入数组中的每个数字。digit = (num // div) % 10：确定当前数字对应于当前位数的数字（例如，对于个位，div = 1；对于十位，div = 10 等）。bucket[digit].append(num)：将数字放入相应的桶中。
arr = [x for x in bucket for x in x]：将桶中的数字按顺序重新组合成一个新的数组。div *= 10：将除数乘以 10，以便在下一次循环中处理下一位。
下面是举列：
假设我们有一个随机生成的数组old_list = [73, 49, 81, 26, 57, 64]
-
确定最大数和初始除数：
max_num = max(arr)，这里max_num = 81。div = 1。
-
第一次循环（个位排序）：
- 创建 10 个空桶：
bucket = [[] for _ in range(10)]。 - 遍历输入数组中的每个数字：
- 对于数字 73，
digit = (73 // div) % 10 = 3，将 73 放入第 3 个桶中。 - 对于数字 49，
digit = (49 // div) % 10 = 9，将 49 放入第 9 个桶中。 - 以此类推，将所有数字根据个位数字放入相应的桶中。
- 对于数字 73，
- 重新组合数组：
arr = [x for x in bucket for x in x]。此时可能得到[81, 26, 49, 57, 73, 64]（如果个位数字没有重复，顺序可能不同）。
- 创建 10 个空桶：
-
第二次循环（十位排序）：
div *= 10，现在div = 10。- 再次创建 10 个空桶。
- 遍历重新组合后的数组：
- 对于数字 81，
digit = (81 // div) % 10 = 8，将 81 放入第 8 个桶中。 - 对于数字 26，
digit = (26 // div) % 10 = 2，将 26 放入第 2 个桶中。 - 以此类推，将所有数字根据十位数字放入相应的桶中。
- 对于数字 81，
- 重新组合数组。此时得到排序后的结果
[26, 49, 57, 64, 73, 81]。
9希尔排序
希尔排序也称为 “缩小增量排序”，它是对插入排序的一种改进，通过将原始数据分成多个子序列，分别进行插入排序，逐步减少子序列的间隔，最终实现对整个序列的排序。
代码如下：
import numpy as np
def shell(arr):
n = len(arr)
gap = n//2
while gap > 0 :
for i in range(gap,n):
temp = arr[i]
j = i
while j >= gap and arr[j-gap] >temp:
arr[j] = arr[j-gap]
j-=gap
arr[j] = temp
gap //=2
return arr
old_list = np.random.randint(100,size=6)
print(f"未排序的列表{old_list}")
new_list = shell(old_list)
print(f"排完序后的列表{[int(x) for x in new_list]}")代码详解：
-
shell函数：n = len(arr)：获取输入数组的长度。gap = n // 2：初始化间隔为数组长度的一半。while gap > 0：当间隔大于 0 时，进行循环。for i in range(gap, n)：从间隔位置开始遍历数组。temp = arr[i]：保存当前要插入的元素。j = i：设置一个指针j，初始值为当前要插入的元素的索引。while j >= gap and arr[j - gap] > temp：当j大于等于间隔且当前位置的元素大于要插入的元素时，进行循环。arr[j] = arr[j - gap]：将较大的元素向后移动间隔的位置。j -= gap：更新指针j，继续向前比较。arr[j] = temp：将保存的要插入的元素放置在正确的位置。gap //= 2：每次循环结束后，将间隔缩小一半。
下面是举例：
假设我们有一个随机生成的数组old_list = [58, 33, 72, 46, 29, 67]
-
初始设置：
n = 6，即数组长度为 6。gap = n // 2 = 3。
-
第一次以间隔为 3 进行排序：
- 子序列为
[58, 46]、[33, 29]、[72, 67]。 - 对于
[58, 46]，58 大于 46，交换得到[46, 58]。 - 对于
[33, 29]，33 大于 29，交换得到[29, 33]。 - 对于
[72, 67]，72 大于 67，交换得到[67, 72]。 - 此时数组变为
[46, 29, 67, 58, 33, 72]。
- 子序列为
-
缩小间隔：
gap //= 2 = 1。
-
以间隔为 1 进行插入排序：
- 从第二个元素开始，逐个插入到已排序的部分中。
- 对于 29，与 46 比较，29 小于 46，交换得到
[29, 46, 67, 58, 33, 72]。 - 对于 67，无需交换。
- 对于 58，无需交换。
- 对于 33，与 58 比较，33 小于 58，交换；继续与 46 比较，33 小于 46，交换；继续与 29 比较，无需交换，得到
[29, 33, 46, 58, 67, 72]。
最终得到排序后的数组[29, 33, 46, 58, 67, 72]