python实现快速排序算法。

简介: 【2月更文挑战第9天】【2月更文挑战第23篇】python实现快速排序算法。

快速排序(Quick Sort)是一种分治的排序算法。它会选择数组中的一个元素作为枢轴(pivot),然后将数组中所有其他元素与该枢轴元素进行比较,按照顺序将其放在枢轴的两边。
以下是使用 Python 实现快速排序的代码:

# 快速排序函数
def quickSort(arr, low, high):
    if low < high:
        # 找到枢轴的正确位置
        pi = partition(arr, low, high)
        # 对左右子数组分别进行递归排序
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)

# 分治函数,用于确定枢轴的正确位置
def partition(arr, low, high):
    pivot = arr[high]
    i = (low - 1)

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return (i + 1)

# 测试示例
arr = [10, 80, 30, 90, 40, 50, 70]
n = len(arr)

quickSort(arr, 0, n - 1)

print("排序后的数组:")
for item in arr:
    print(item)

这段代码实现了快速排序的程序,其平均时间复杂度为$O(nlogn)$,空间复杂度为$O(logn)$。在这段代码中,我们首先使用quickSort函数来递归地对数组进行排序。然后,partition函数用于确定枢轴的正确位置,并将比枢轴小的元素放在左边,比枢轴大的元素放在右边。最后,我们使用一个示例数组来测试快速排序算法,并输出排序后的结果。

希望这段代码能够帮助到你,如果你还有其他疑问,请随时向我提问。😄

相关文章
|
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
|
14天前
|
搜索推荐 Java
Java基础(快速排序算法)
Java基础(快速排序算法)
21 4
|
17天前
|
搜索推荐 算法 编译器
【数据结构】八大排序之快速排序算法
【数据结构】八大排序之快速排序算法
35 4
|
19天前
|
算法 Python
数据结构与算法 经典排序方法(Python)
数据结构与算法 经典排序方法(Python)
23 0