# Python 一网打尽＜排序算法＞之从希尔排序算法的分治哲学开始

## 1. 前言

&#x5E0C;&#x5C14;&#x5F52;&#x5E76;&#x5FEB;&#x901F;排序算法也可归为同一类，它们的共同点都是建立在分治思想之上。把大问题分拆成小问题，解决所有小问题后，再合并每一个小问题的结果，最终得到对原始问题的解答。

[En]

The algorithm of divide and conquer is very philosophical: as our ancestors said, it must be divided for a long time, and the purpose of separation is for a better merger.

• 分解问题：将一个需要解决的、看起很复杂 &#x539F;&#x59CB;&#x95EE;&#x9898; 分拆成很多独立的 &#x5B50;&#x95EE;&#x9898;&#x5B50;&#x95EE;&#x9898;&#x539F;&#x59CB;&#x95EE;&#x9898;有相似性。

如：一个数列的局部（小问题）有序，必然会让数列最终（原始问题）有序。

• 求解子问题：子问题除了与原始问题具有相似性，也具有独立性，即所有子问题都可以独立求解。
• 合并子问题：合并每一个子问题的求解结果最终可以得到原始问题的解。

## 2. 希尔排序

• 插入排序算法的排序思想是尽可能减少数字之间的交换次数。
[En]

the sorting idea of the insertion sorting algorithm is to * reduce the number of exchanges between numbers as much as possible.

• 一般来说，掉期的时间大约是搬家的三倍。这就是插入排序可能优于气泡排序的原因。
[En]

in general, swapping takes about three times as long as moving. This is why insert sorting is likely to outperform bubble sorting.*

Hill排序算法本质上是插入排序，或者说是插入排序的改进。

[En]

Hill sorting algorithm is essentially insertion sorting, or an improvement of insertion sorting.

• 逻辑上将原始序列切成多个子系列。
[En]

logically cut the original sequence into a number of sub-series.*

• 使用插入排序算法对每个子列进行排序。
[En]

sort each subcolumn using the insert sort algorithm.*

• 当所有子序列完成后，最后一次按插入算法对原始序列进行排序。
[En]

when all the subseries are completed, the original sequence is sorted by the insertion algorithm for the last time.*

### 2.1 前后切分

[En]

As shown in the figure above, after sorting the subsequence, if you want to arrange all the numbers in the original sequence from small to large, then almost all the numbers in the latter part have to be moved to the middle of the first part of the number, and the amount of movement is very large.

[En]

This method is difficult to achieve a locally ordered normal distribution of numbers, because the position of numbers does not change much.

[En]

The position change of the number before and after slicing is shown in the following figure. Compared with the image above, the position change of the number is very limited and is limited in a very narrow range. In other words, the result of the sub-problem has little influence on the result of the final problem.

### 2.2 增量切分

[En]

The incremental segmentation adopts the interval segmentation scheme, which may make the number locally ordered with normal distribution.

[En]

On this basis, the number of insertion sorting is much less.

[En]

The following figure is the change of the position of the number after incremental segmentation, you can see that almost all the numbers have a position change, and the span of the position change is large. There is a tendency towards order as a whole.

[En]

When implementing the Hill sorting algorithm, the best solution is to initialize an incremental value first, split and sort, and then reduce the incremental value, repeatedly until the incremental value is equal to 1 (that is, insert sorting for the original sequence as a whole).

希尔排序
def shell_sort(nums):
# 增量
increment = len(nums) // 2
# 新数列
while increment > 0:
# 增量值是多少，则切分的子数列就有多少
for start in range(increment):
insert_sort(nums, start, increment)
# 修改增量值，直到增量值为 1
increment = increment // 2

def insert_sort(nums, start, increment):
for back_idx in range(start + increment, len(nums), increment):
for front_idx in range(back_idx, 0, -increment):
if nums[front_idx] < nums[front_idx - increment]:
nums[front_idx], nums[front_idx - increment] = nums[front_idx - increment], nums[front_idx]
else:
break

nums = [3, 9, 8, 1, 6, 5, 7]
shell_sort(nums)
print(nums)


[En]

Here is a puzzling point of view: * is it possible that the time complexity of one insertion sort is higher than that of multiple insertion sorting? *

## 3. 归并排序

[En]

The merging and sorting algorithm is also based on the idea of divide and conquer. Like Hill sorting, you need to split the original sequence, but the scheme is different.

[En]

Compared with Hill sorting, merging subproblems, solving subproblems, the process dividing line of merging subproblems is very clear. It can be said that merger and sorting can better explain what is the idea of partition and rule.

### 3.1 分解子问题

[En]

The decomposition process of the merge sorting algorithm adopts a dichotomy scheme.

• 把原始数列一分为二。
• 然后在已经切分后的子数列上又进行二分。
• 如此反复，直到子数列不能再分为止。 如下图所示：

[En]

In the following code, the original sequence is segmented using a recursive algorithm, and the segmentation process is observed through the output:

切分原数列
def split_nums(nums):
print(nums)
if len(nums) > 1:
# 切分线，中间位置
sp_line = len(nums) // 2
split_nums(nums[0:sp_line])
split_nums(nums[sp_line:])

nums = [3, 9, 8, 1, 6, 5, 7]
split_nums(nums)


[3, 9, 8, 1, 6, 5, 7]
[3, 9, 8]
[3]
[9, 8]
[9]
[8]
[1, 6, 5, 7]
[1, 6]
[1]
[6]
[5, 7]
[5]
[7]


### 3.3 合并排序

• 数字 1 和 数字 5 比较，5 大于 1 ，数字 1 先位于合并数列中。

• 数字 3 与数字 5 比较，数字 3 先进入合并数列中。

• 数字 8 和数字 5 比较，数字 5 进入合并数列中。

[En]

Compare the size of the first number from beginning to end, and finally, you can ensure that the merged sequence is orderly.

• 没有额外的存储空间：所有最终合并的排序数字都存储在其中一个系列中。
[En]

No additional storage space: all the final merged sorted numbers are stored in one of the series.*

def merge_sort(nums01, nums02):    # 为 2 个数列创建 2 个指针    idx_01 = 0    idx_02 = 0    while idx_01 < len(nums01) and idx_02 < len(nums02):        if nums01[idx_01] > nums02[idx_02]:            # 这里不额外增加存储空间，如果数列 2 中的值大于数字 1 的插入到数列 1 中            nums01.insert(idx_01, nums02[idx_02])            idx_02 += 1        # 数列 1 的指针向右移动        idx_01 += 1    # 检查 nums02 中的数字是否已经全部合并到 nums01 中    while idx_02 < len(nums02):        nums01.append(nums02[idx_02])        idx_02 += 1nums01 = [1, 2, 8, 9]nums02 = [5, 6, 7, 12, 15]merge_sort(nums01, nums02)将合并后的数字存储在第一序列中。<details><summary>*<font color='gray'>[En]</font>*</summary>*<font color='gray'>The merged numbers are stored in the first sequence.</font>*</details>print(nums01)'''输出结果：[1,2,5,6,7,8,9,12,15]'''
• 添加一个空序列以保存最终合并的数字。
[En]

add an empty sequence to hold the final merged numbers.*

使用附加数列nums=[]def merge_sort(nums01, nums02):    # 为 2 个数列创建 2 个指针    idx_01 = 0    idx_02 = 0    k=0    while idx_01 < len(nums01) and idx_02 < len(nums02):        if nums01[idx_01] > nums02[idx_02]:            nums.append(nums02[idx_02])            idx_02 += 1        else:            nums.append(nums01[idx_01])            idx_01 += 1        k+=1    # 检查是否全部合并    while idx_02 < len(nums02):        nums.append(nums02[idx_02])        idx_02 += 1    while idx_01 < len(nums01):        nums.append(nums01[idx_01])        idx_01 += 1nums01 = [1, 2, 8, 9]nums02 = [5, 6, 7, 12, 15]merge_sort(nums01, nums02)print(nums)

[En]

The previous step is to explain the segmentation and merge logic step by step, and now the segmentation and merge logic are combined into one to complete the implementation of the merger algorithm:

def merge_sort(nums):
if len(nums) > 1:
# 切分线，中间位置
sp_line = len(nums) // 2
nums01 = nums[:sp_line]
nums02 = nums[sp_line:]
merge_sort(nums01)
merge_sort(nums02)

# 为 2 个数列创建 2 个指针
idx_01 = 0
idx_02 = 0
k = 0
while idx_01 < len(nums01) and idx_02 < len(nums02):
if nums01[idx_01] > nums02[idx_02]:
# 合并后的数字要保存到原数列中
nums[k] = nums02[idx_02]
idx_02 += 1
else:
nums[k] = nums01[idx_01]
idx_01 += 1
k += 1
# 检查是否全部合并
while idx_02 < len(nums02):
nums[k] = nums02[idx_02]
idx_02 += 1
k += 1
while idx_01 < len(nums01):
nums[k] = nums01[idx_01]
idx_01 += 1
k += 1

nums = [3, 9, 8, 1, 6, 5, 7]
merge_sort(nums)
print(nums)


## 4. 基数排序

• 先提供一个长度为 10 的新空数列（本文也称为排序数列）。

为什么新空数列的长度要设置为 10？等排序完毕，相信大家就能找到答案。

。将原系列中的数字转移到新的空系列中，并转储方案：

[En]

. Transfer the numbers from the original series to a new empty series, and dump the scheme:

nums 中的数字 3 存储在新数列索引号为 3 的位置。

nums 中的数字 9 存储在新数列索引号为 9 的位置。

nums 中的数字 8 存储在新数列索引号为 8 的位置。

……

[En]

As can be seen from the above figure, the position where the numbers in the original series are transferred to the sorted series is the position indicated by the index number represented by the number. Obviously, after the rollover, the new sequence is a sequenced sequence.

原数列
nums = [3, 9, 8, 1, 6, 5, 7]

sort_nums=[0]*(max(nums)+1)
for i in nums:
sort_nums[i]=i

print([i for i in sort_nums if i!=0])
'''

[1,3,5,6,7,8,9]
'''


[En]

Using the above scheme to create new empty data, if the interval between numbers is large, the space waste of the new series is very large.

• 它首先按照每个数字中的数字存储。单个数字1存储在位置1，9存储在位置9。如下图所示：
[En]

it is first stored according to the number in each digit. A single digit of 1 is stored in a location of 1, and 9 is stored in a location of 9. As shown below:*

• 把存放在 排序数列中的数字按顺序重新拿出来，这时的数列顺序变成 nums=[1&#xFF0C;51&#xFF0C;2&#xFF0C;32&#xFF0C;13&#xFF0C;4&#xFF0C;45&#xFF0C;8&#xFF0C;99]
• 根据十位数字的数字，将重组后的数列中的数字重新存储到排序后的数列中。
[En]

re-store the numbers in the reorganized series into the sorted series according to the numbers in the ten digits.*

[En]

Cardinality sort, it has the flavor of life!

nums = [1, 98, 51, 2, 32, 4, 99, 13, 45]

m = max(nums)

l = len(str(m))

for i in range(l + 1):
# 排序数列，也是桶
sort_nums = [[] for _ in range(10)]
for n in nums:
# 分解数字个位上的数字
g_s = (n // 10 ** i) % 10
# 根据个位上的数字找到转存位置
sub_nums = sort_nums[g_s]
sub_nums.append(n)
# 合并数据
nums = []
for l in sort_nums:
nums.extend(l)
print(nums)
'''

[1, 2, 4, 13, 32, 45, 51, 98, 99]
'''


## 5. 总结

[En]

Partition is very philosophical. When you encounter difficulties, you should try to find the weak point of the problem, and then break through little by little.

[En]

When we encounter difficulties, teachers always advise us like this.

[En]

In fact, divide and conquer and the idea of component design in project development also have the same work and different songs.

Original: https://www.cnblogs.com/guo-ke/p/16151790.html
Author: 一枚大果壳
Title: Python 一网打尽＜排序算法＞之从希尔排序算法的分治哲学开始

(0)

### 大家都在看

• #### 全自动化机器学习建模！效果吊打初级炼丹师！ ⛵

💡 作者：韩信子@ShowMeAI📘 机器学习实战系列：https://www.showmeai.tech/tutorials/41📘 本文地址：https://www.showm…

Python 2023年10月25日
0100

Http协议是万维网数据通信的基础。 它协议定义了从指定URL中检索不同数据的方法。 下表概括了不同的 http 方法 方法描述GET将数据以未加密的形式发送到服务器，这最常用的方…

Python 2023年8月11日
087
• #### 一个高性能跨平台基于Python的Waitress WSGI Server的介绍！

Python 2023年5月24日
0219
• #### 01_Django-介绍-项目结构-URL和视图函数

01_Django-介绍-项目结构-URL和视图函数 视频🔗：https://www.bilibili.com/video/BV1vK4y1o7jH博客🔗：https://blog…

Python 2023年5月25日
0161
• #### 瞧瞧别人家的API接口，那叫一个优雅

在实际工作中，我们需要经常跟第三方平台打交道，可能会对接第三方平台API接口，或者提供API接口给第三方平台调用。 那么问题来了，如果设计一个优雅的API接口，能够满足：安全性、可…

Python 2023年10月12日
0100
• #### python学习 –DataFrame数据清洗（空值、重复值）

目录 空值的处理 1、检查是否有空值 2、统计空值的数量 3、删除空值 4、填补空值 用value参数替换空值 将空值替换成上一列的值 将空值替换成上一行的值 将空值替换成下一列的…

Python 2023年8月8日
0123
• #### pytest 重试_pytest中的重试和超时 pytest-rerunfailures @pytest.mark.flaky(reruns=2)

首先安装pytest-rerunfailures插件，之后加上注解@pytest.mark.flaky(returns=2) reruns：代表 当case 执行失败的时候 回溯失…

Python 2023年9月11日
0135
• #### Linux NTP工具的基本使用

404. 抱歉，您访问的资源不存在。 可能是网址有误，或者对应的内容被删除，或者处于私有状态。 代码改变世界，联系邮箱 contact@cnblogs.com 弹尽粮绝，会员救园：…

Python 2023年10月12日
098
• #### 就Python库比如pygame,wx等包安装错我问题解决办法

在我们导入引用一个python游戏时，会出现丢失库的问题，会发现我们pygame，wx等库没有，如下图所示： 我们看看我们的pip库正常不： 这里是正常的，我们用pycharm的提…

Python 2023年9月23日
0116
• #### 几种python存储数据(海量数据)的方式及读取时间对比

先说在本机环境下的测试结果，仅供参考，其中单次调用时测试了10次，多次调用时测试了5次： 单次读取时，h5py文件整体平均读取速度最快，pkl文件整体平均读取最慢 多次读取(循环读…

Python 2023年8月23日
0151
• #### 全网首发！精选32个最新Python实战项目(附源码)，拿走就用！

Python是目前最好的编程语言之一。由于其可读性和对初学者的友好性，已被广泛使用。那么要想学会并掌握Python，可以实战的练习项目是必不可少的。接下来，我将给大家介绍32个非常…

Python 2023年8月2日
0169
• #### NNDL 作业3：分别使用numpy和pytorch实现FNN例题

过程推导 – 了解BP原理 数值计算 – 手动计算，掌握细节 代码实现 – numpy手推 + pytorch自动 过程推导、数值计算，以下三种…

Python 2023年8月28日
0126
• #### 简易计时器开发

事情是这样的，学校给了一个网页，让我们去学习，网页超过5分钟无操作会自动跳出，需要一个定时器来提醒我们每隔一段时间去操作网页，我在网上查了几个定时器，都不太符合要求，于是自己动手做…

Python 2023年9月17日
0110
• #### Python数据可视化 | 1、数据可视化流程

目录 1、数据准备 2、确定图表 3、分析迭代 4、输出结论 5、小结 6、作业 1、数据准备 数据规模：数据分组、数据采样（处理大数据时候尤为需要） 数据类型：数值数据、分类数据…

Python 2023年8月20日
0164
• #### [python]使用faker库生成测试数据

python的faker库基本介绍，示例使用faker生成数据并写入到MySQL 简介 Faker库可用于随机生成测试用的虚假数据。可生成的数据参考底部的参考链接。 安装： pyt…

Python 2023年6月12日
0141
• #### pytest如何防止频繁打开浏览器

1、问题描述：登录系统后，进入A模块，点击【新增】按钮，执行新增操作的用例，我希望每次都是重新从新增按钮页面开始操作，而不需从新打开浏览器，进行登录，然后进入A模块等操作 初步解决…

Python 2023年9月11日
0128