python实现归并排序算法。

简介: 【2月更文挑战第9天】【2月更文挑战第24篇】python实现归并排序算法。

归并排序(Merge Sort)是建立在归并操作上的一种有效、稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
以下是使用 Python 实现归并排序的代码:

# 归并排序函数
def mergeSort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = mergeSort(arr[:mid])
    right = mergeSort(arr[mid:])

    return merge(left, right)

# 合并两个已排序的子数组为一个已排序的数组
def merge(left, right):
    merged = []
    left_index = 0
    right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1

    merged.extend(left[left_index:])
    merged.extend(right[right_index:])

    return merged

# 测试示例
arr = [12, 11, 13, 5, 6]
sorted_arr = mergeSort(arr)
print("排序后的数组:", sorted_arr)

在这个示例中,我们首先定义了mergeSort函数,它采用分治法将数组分为两半,对每一半进行排序,然后合并它们。merge函数用于合并两个已排序的子数组。最后,我们使用一个示例数组来测试归并排序算法,并输出排序后的结果。

归并排序的时间复杂度为$O(nlogn)$,空间复杂度为$O(n)`。它是一种稳定的排序算法,在实际应用中表现良好。

如果你对归并排序还有其他疑问,或者需要进一步的解释,请随时告诉我。🤗

相关文章
|
27天前
|
机器学习/深度学习 算法 Python
请解释Python中的随机森林算法以及如何使用Sklearn库实现它。
【2月更文挑战第28天】【2月更文挑战第101篇】请解释Python中的随机森林算法以及如何使用Sklearn库实现它。
|
13天前
|
机器学习/深度学习 算法 搜索推荐
Machine Learning机器学习之决策树算法 Decision Tree(附Python代码)
Machine Learning机器学习之决策树算法 Decision Tree(附Python代码)
|
25天前
|
机器学习/深度学习 算法 数据挖掘
请解释Python中的决策树算法以及如何使用Sklearn库实现它。
决策树是监督学习算法,常用于分类和回归问题。Python的Sklearn库提供了决策树实现。以下是一步步创建决策树模型的简要步骤:导入所需库,加载数据集(如鸢尾花数据集),划分数据集为训练集和测试集,创建`DecisionTreeClassifier`,训练模型,预测测试集结果,最后通过`accuracy_score`评估模型性能。示例代码展示了这一过程。
|
26天前
|
机器学习/深度学习 算法 数据可视化
请解释Python中的K-means聚类算法以及如何使用Sklearn库实现它。
【2月更文挑战第29天】【2月更文挑战第104篇】请解释Python中的K-means聚类算法以及如何使用Sklearn库实现它。
|
3天前
|
算法 数据可视化 数据挖掘
使用Python实现DBSCAN聚类算法
使用Python实现DBSCAN聚类算法
135 2
|
5天前
|
算法 数据可视化 数据挖掘
使用Python实现K均值聚类算法
使用Python实现K均值聚类算法
14 1
|
8天前
|
机器学习/深度学习 算法 Python
使用Python实现随机森林算法
使用Python实现随机森林算法
17 0
|
17天前
|
搜索推荐 算法
【数据结构】八大排序之归并排序算法
【数据结构】八大排序之归并排序算法
20 5
|
19天前
|
算法 Python
数据结构与算法 经典排序方法(Python)
数据结构与算法 经典排序方法(Python)
23 0
|
24天前
|
算法 搜索推荐 测试技术
python排序算法及优化学习笔记1
python实现的简单的排序算法,以及算法优化,学习笔记1
33 1