归并排序的Python程序
已发表: 2023-01-31作为一种多范式编程语言，具有结构化、面向对象的设计方法和简单整洁的句法和文法，Python 正迅速成为从事各种复杂性和规模项目的程序员的首选语言。
Python 提供了一个预构建算法的模块化库，允许其用户执行各种操作，这些操作可以帮助他们自己完成任务，或者作为实现更大、更复杂目标的一个步骤。 一种更流行的此类算法是启用合并排序功能的算法。
目录
什么是归并排序？
它是一种通用的排序技术，使用户能够从任何来源获取任何类型的随机数据集，并将其分成重复的阶段，直到最终将其分解为各个组成部分——一种递归技术，通常称为“分而治之”的方法。
然后，该算法将各个组件放在一起——再次重复阶段——但在沿途的每个阶段将它们分类为预先确定的逻辑序列，使用基本比较和交换，直到整个数据系列按照所需的逻辑序列重新构建.
在 upGrad 查看我们的其他数据科学课程。
分而治之技术
以字母表中字母的随机数据集为例：N、H、V、B、Q、D、Z、R。
步骤 1 ：原始数据集首先被分成两组，如下所示：
N, H, V, B Q, D, Z, R
第 2 步：两个结果数组都进一步细分如下：
N, H V, B Q, D Z, R
第 3 步：最后，所有四个数组都被进一步拆分，直到整个数据系列被分解成各个部分：
N H V B Q D Z R
然后该过程反转，各个数据点现在开始以分阶段的方式合并。 但是在这个合并过程中，每个子数组中的每个元素都会被评估和交换，以便它们按照逻辑顺序（字母顺序）对自己进行排序，如下所示：
第 4 步：单个元素合并成对，同时根据需要交换位置以形成正确的序列：
H, N B, V D, Q R, Z
第五步：合并和排序的递归过程继续到下一次迭代：
B、H、N、V D、Q、R、Z
第 6 步：整个数据系列最终按其逻辑字母顺序重组：
B、D、H、N、Q、R、V、Z
探索我们的热门数据科学课程
| IIITB 的数据科学执行研究生课程 | 商业决策数据科学专业证书课程 | 亚利桑那大学数据科学硕士 |
| IIITB 的数据科学高级证书课程 | 马里兰大学数据科学和商业分析专业证书课程 | 数据科学课程 |
合并排序实现
在 Python 中有两种实现合并排序的方法。 自上而下的方法和自下而上的方法。
自上而下的方法：
更常用的自上而下的方法是上面描述的方法。 它需要更长的时间并占用更多的内存，因此在处理较小的数据集时效率低下。 但是，它要可靠得多，尤其是在应用于大型数据集时。
阅读我们流行的数据科学文章
| 数据科学职业道路：综合职业指南 | 数据科学职业发展：工作的未来就在这里 | 为什么数据科学很重要？ 数据科学为企业带来价值的 8 种方式 |
| 数据科学对管理者的相关性 | 每个数据科学家都应该拥有的终极数据科学备忘单 | 你应该成为数据科学家的 6 大理由 |
| 数据科学家的一天：他们做什么？ | 神话破灭：数据科学不需要编码 | 商业智能与数据科学：有什么区别？ |
输入代码：
def merge_sort (inp_arr):
大小 = len(inp_arr)
如果大小 > 1：
中间 = 大小 // 2
left_arr = inp_arr(:middle)
rIght_arr = inp_arr（中间：）
merge_sort(left_arr)
合并_sort（right_arr）
我 = 0
j = 0
k = 0
（其中i和j分别是遍历数据序列左右两边的迭代器，k是整个数据序列的迭代器）。
left_size = len(left_arr)
右 _size = len(right_arr)
当 i < left_size 且 j < right size 时：
如果 left_arr(i) < right_arr(j):
inp_arr(k) – left_arr(i)
我 >= 1
别的：
inp_arr(k) = right_arr(j)
j += 1
k += 1
当我 < left_size:
inp_arr (k) = left_arr(i)
我 += 1
k += 1
而 j < right_size:
inp_arr (k) = right_arr(j)
j += 1
k += 1
inp_arr = (N, H, V, B, Q, D, Z, R)
打印（：输入数组：\n”）
打印（inp_arr）
merge_sort (inp_arr)
打印（“排序数组：\n”）
打印（inp_arr）
输出：
输入数组：N、H、V、B、Q、D、Z、R
输出数组：B、D、H、N、Q、R、V、Z
自下而上的方法：
自下而上的方法速度更快，占用的内存更少，并且可以高效地处理较小的数据集，但在处理大型数据集时可能会遇到问题。 因此使用频率较低。
输入代码：
def 合并（左，右）：
结果 = [] x, y = 0, 0
对于范围内的 k（0，len（左）+ len（右））：
if i == len(left): # 如果在上半场结束时，
result.append(right[j]) # 添加第二部分的所有值
j += 1
elif j == len(right): # 如果在下半场结束时，
result.append(left[x]) # 添加第一半的所有值
我 += 1
elif 右 [j] < 左 [i]:
结果.追加（右[j]）
j += 1
别的：
结果.追加（左[i]）
我 += 1
返回结果
def mergesort（ar_list）：
长度 = len(ar_list)
大小 = 1
而大小 < 长度：
size+=size # 按照描述初始化为 2
对于范围内的位置（0，长度，大小）：
开始=位置
中间 = 位置 + 整数（大小 / 2）
结束 = 位置 + 大小
left = ar_list[开始：mid] right = ar_list[mid：end]
ar_list[开始：结束] = 合并（左，右）
返回 ar_list
ar_list = [N, H, V, B, Q, D, Z, R] print(mergesort(ar_list))
输出：
输入数组：N、H、V、B、Q、D、Z、R
输出数组：B、D、H、N、Q、R、V、Z
适用于更复杂的真实数据集的合并排序实现
让我们将自上而下的方法应用于印度的四辆随机越野车：
品牌 | 模型 | 千万卢比的展厅前价格 |
| 吉普车 | 牧马人 | 0.58 |
| 福特 | 努力 | 0.35 |
| 捷豹路虎 | 路虎揽胜运动版 | 2.42 |
| 奔驰 | G级 | 1.76 |
输入代码：
类车：
def __init__（自我，品牌，型号，价格）：
self.brand = 品牌
self.model = 模型
self.price = 价格
定义__str __（自我）：
return str.format(“品牌：{}，型号：{}，价格：{}”，self.brand,
self.model, self.price)
def merge(list1, i, j, k, comp_fun):
left_copy = list1[i:k + 1]
r_sublist = list1[k+1:r+1]
left_copy_index = 0
j_sublist_index = 0
排序索引=我
而left_copy_index < len(left_copy)和j_sublist_index <
len(j_sublist):
如果comp_fun(left_copy[left_copy_index], j_sublist[j_sublist_index]):
list1[sorted_index] = left_copy[left_copy_index]
left_copy_index = left_copy_index + 1
其他：
list1[sorted_index] = j_sublist[j_sublist_index]
j_sublist_index = j_sublist_index + 1
排序索引 = 排序索引 + 1
而left_copy_index < len(left_copy):
list1[sorted_index] = left_copy[left_copy_index]
left_copy_index = left_copy_index + 1
排序索引 = 排序索引 + 1
而j_sublist_index < len(j_sublist):
list1[sorted_index] = j_sublist[j_sublist_index]
j_sublist_index = j_sublist_index + 1
排序索引 = 排序索引 + 1
def merge_sort(list1, i, j, comp_fun):
如果我 >= j:
返回
k = (i + j)//2
merge_sort(list1, i, k, comp_fun)
merge_sort(list1, k + 1, j, comp_fun)
合并（list1，i，j，k，comp_fun）
car1 = Car(“Jeep”, “Wrangler”, 0.58)
car2 = 汽车（“福特”，“奋进”，0.35）
car3 = Car(“Jaguar Land Rover”, “Range Rover Sport”, 1.76)
car4 = Car(“奔驰”, “G级”, 2.42)
list1 = [car1, car2, car3, car4]
merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.brand < carB.brand)
打印（“按品牌分类的汽车：”）
对于列表 1中的汽车：
打印（汽车）
打印()
merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.price< carB.price)
打印（“汽车按价格排序：”）
对于列表 1中的汽车：
打印（汽车）
输出：
按品牌分类的汽车：
福特奋进号
捷豹路虎揽胜运动版
吉普牧马人
奔驰G级
按价格排序的汽车：
福特奋进号
吉普牧马人
捷豹路虎揽胜
奔驰G级
您可以通过马里兰大学的 upGrad 数据科学和商业分析专业证书学习 Python 的理论和实践方面。 本课程可帮助您从头开始学习 Python。 即使您是编程和编码的新手，upGrad 也会为您提供为期两周的预备课程，以便您掌握编程的基础知识。 在从事多个行业项目时，您将学习各种工具，如 Python、SQL 等。
