常用排序算法汇总—Python版

这篇具有很好参考价值的文章主要介绍了常用排序算法汇总—Python版。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

常用排序算法汇总—Python版

一、选择排序

1. 原理:

选择排序(Selection Sort)是一种简单直观的排序算法,它的基本思路是将数组按顺序分成已排序部分和未排序部分,然后每次从未排序部分中选择出最小的元素,将其添加到已排序部分的末尾。重复这个过程,直到未排序部分为空,整个数组都已排好序。

2. 代码

def selection_sort(lst):
    n = len(lst)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if lst[j] < lst[min_idx]:
                min_idx = j
        lst[i], lst[min_idx] = lst[min_idx], lst[i]
    return lst

arr = [3, 5, 8, 1, 2, 9, 4, 7, 6]
sorted_arr = selection_sort(arr)
print(sorted_arr)

二、冒泡排序

1. 原理:

冒泡排序(Bubble Sort)是一种简单直观的排序算法,它的基本思路是重复地遍历数列,一次比较两个元素,如果它们的顺序错误,就交换位置。每一次遍历都将最大或最小的元素“浮”到了最顶端,因此得名冒泡排序。

2. 代码

def bubble_sort(lst):
    n = len(lst)
    for i in range(n-1):
        for j in range(n-i-1):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
    return lst


lst = [8, 3, 5, 1, 2, 7, 6, 4]
sorted_lst = bubble_sort(lst)
print(sorted_lst)  # 输出 [1, 2, 3, 4, 5, 6, 7, 8]

三、插入排序

1. 原理:

插入排序(Insertion Sort)是一种简单直观的排序算法,它的基本思路是将未排序的元素一个一个插入到已经排序的部分中适当的位置上去。它的实现过程是将一个待排序的列表分成两部分,第一部分为已排序的,第二部分为未排序的,初始状态下第一部分为列表中的第一个元素,而第二部分为除第一个元素外的其他元素。在排序过程中,我们是从未排序部分中取出一个元素,将它插入到已排序部分中去。重复这个过程,直到未排序部分为空,整个列表都已排好序。

2. 代码

def insertion_sort(lst):
    n = len(lst)
    for i in range(1, n):
        key = lst[i]
        j = i - 1
        while j >= 0 and lst[j] > key:
            lst[j+1] = lst[j]
            j -= 1
        lst[j+1] = key
    return lst



lst = [8, 3, 5, 1, 2, 7, 6, 4]
sorted_lst = insertion_sort(lst)
print(sorted_lst)  # 输出 [1, 2, 3, 4, 5, 6, 7, 8]

该函数的主要实现过程如下:

  1. 遍历整个列表,从下标 i=1 开始,逐步将未排序部分添加到已排序部分中
  2. 选取未排序部分的第一个元素作为 key,将其与已排序部分逐一比较
  3. 如果 key 小于已排序部分的某一个元素,则将该元素向后移动一位,继续比较
  4. 如果 key 大于或等于已排序部分的某一个元素,则将 key 插入到该元素后面

四、归并排序

1. 原理:

归并排序(Merge Sort)是一种基于分治思想的排序算法,它的基本思路是将数组分成两个等长的部分,分别对这两部分进行递归排序,然后将排好序的两个子数组合并起来。因为归并排序的实现过程中需要开辟额外的空间来存储临时数组,所以归并排序不是基于比较排序的最优算法,但归并排序的时间复杂度通常很优秀,表现稳定。

2. 代码

def merge_sort(arr):
    # 递归终止条件,数组长度为 1
    if len(arr) == 1:
        return arr

    # 将数组一分为二,并递归对两个子数组进行排序
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # 对排好序的子数组进行归并操作
    sorted_arr = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1

    sorted_arr += left[i:]
    sorted_arr += right[j:]

    return sorted_arr




lst = [8, 3, 5, 1, 2, 7, 6, 4]
sorted_lst = merge_sort(lst)
print(sorted_lst)  # 输出 [1, 2, 3, 4, 5, 6, 7, 8]

该函数的主要实现过程如下:

  1. 如果数组长度为 1,直接返回该数组(递归终止条件)
  2. 将数组一分为二,并递归对左右两个子数组进行排序,最终返回排好序的子数组
  3. 对排好序的子数组进行归并操作,通过比较两个子数组的首元素,不断将更小的元素添加到一个新的数组中,最终将子数组中剩余的元素也加入到新数组中来
  4. 返回归并后的新数组

五、快速排序

1. 原理

快速排序是一种基于分治思想的排序算法,它的基本思路是先找到一个基准值(pivot),将数组划分为两部分,使得左半部分的所有元素小于等于基准值,右半部分的所有元素大于基准值。然后对左右两个部分分别递归地进行同样的处理,直到整个数组有序。

2. 代码

def quick_sort(arr):
    # 如果数组长度小于等于 1,直接返回
    if len(arr) <= 1:
        return arr

    # 选择第一个元素为基准值,随机选择也是一种优化方法
    pivot = arr[0]

    # 使用列表推导式获取左侧和右侧子数组
    left = [x for x in arr[1:] if x <= pivot]
    right = [x for x in arr[1:] if x > pivot]

    # 递归调用快速排序,并将左右子数组拼接起来
    return quick_sort(left) + [pivot] + quick_sort(right)

lst = [8, 3, 5, 1, 2, 7, 6, 4]
sorted_lst = quick_sort(lst)
print(sorted_lst)  # 输出 [1, 2, 3, 4, 5, 6, 7, 8]

该函数的实现并不复杂,思路也比较清晰。主要包含以下步骤:

  1. 如果数组长度小于等于 1,直接返回该数组
  2. 选择第一个元素作为基准值,将数组划分为左右两个子数组,分别为左半部分 left 和右半部分 right
  3. 对左右子数组进行递归调用快速排序,并将将子数组返回值拼接成新数组,注意需要将基准值 pivot 放入中间

六、堆排序

1. 原理

在 heapify() 函数中,函数的参数 n 表示构成二叉树的前 n 个元素,参数 i 表示当前根节点在数组中的位置。该函数的作用是将以 i 为根节点的子树进行堆化,也就是将其变成一个最大堆。在实现过程中,需要不断检查左右子节点和根节点之间的大小关系,并进行必要的交换。

heap_sort() 函数中,先使用叶节点的父节点开始建立一个最大堆,然后对于数组中已经是最大堆的部分,每次提取根节点(最大值),并将其与堆结构末尾的值进行交换。整个排序过程时间复杂度为 O(nlogn)。文章来源地址https://www.toymoban.com/news/detail-432452.html

2. 代码

def heapify(arr, n, i):
    """
    以 i 为根节点,将 arr 中的前 n 个元素构成的二叉树进行堆化
    """
    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]:
        largest = right

    # 如果最大值节点不是 i,那么需要进行交换
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        # 递归堆化交换后的子树
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    # 构建最大堆
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)

    # 逐个取出最大值
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        # 对前 i 个元素进行重新构建最大堆
        heapify(arr, i, 0)

    return arr

lst = [8, 3, 5, 1, 2, 7, 6, 4]
sorted_lst = heap_sort(lst)
print(sorted_lst)  # 输出 [1, 2, 3, 4, 5, 6, 7, 8]

到了这里,关于常用排序算法汇总—Python版的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】Vue3实现选择排序动画效果与原理拆解

    删除有序数组中的重复项 JavaScript实现选择排序 选择排序(Selection Sort)是一种简单的排序算法,其基本思想是从待排序的数据中选择最小(或最大)的元素,然后将其放到已排序的序列的末尾(或开头)。该算法的时间复杂度为O(n^2),其中n是待排序数据的数量,因此在大规

    2024年02月13日
    浏览(38)
  • 【Python排序算法】一文掌握十大排序算法,冒泡排序、插入排序、选择排序、归并排序、计数排序、基数排序、希尔排序和堆排序

    目录 1 冒泡排序(Bubble Sort) 2 插入排序(Insertion Sort) 3 选择排序(Selection Sort) 4. 快速排序(Quick Sort) 5. 归并排序(Merge Sort) 6 堆排序 (Heap Sort) 7 计数排序 (Counting Sort) 8 基数排序 (Radix Sort) 9 希尔排序(Shell Sort) 10 桶排序     1 冒泡排序(Bubble Sort)        冒泡排序

    2024年02月08日
    浏览(55)
  • Python入门教程+项目实战-11.5节: 程序实战-选择排序算法

    目录 11.5.1 排序算法简介 11.5.2 选择排序算法 11.5.3 系统学习python 所谓排序,是指将数据集合中的元素按从小到大的顺序进行排列,或按从大到小的顺序进行排列。前者称为升序排序,后者称为降序排序。在数据结构与算法这门课程中,我们会学习到诸多与排序相关的算法,

    2024年02月02日
    浏览(52)
  • 排序算法:选择排序(直接选择排序、堆排序)

    朋友们、伙计们,我们又见面了,本期来给大家解读一下有关排序算法的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏: C语言:从入门到精通 数据结构专栏: 数据结构 个  人  主  页 : stackY、   目录 前言: 1.选择

    2024年02月09日
    浏览(39)
  • 【数据结构与算法】排序算法:冒泡排序,冒泡排序优化,选择排序、选择排序优化

    目录 一、冒泡排序 1、冒泡排序思想 2、冒泡排序算法的性能分析 代码实现: 二、选择排序 1、选择排序思想 2、选择排序算法的性能分析  代码实现: 1、冒泡排序思想 冒泡排序的基本思想是通过相邻元素之间的比较和交换来逐步将最大(或最小)的元素移到右边(或左边

    2024年01月19日
    浏览(50)
  • 插入/希尔/选择/堆/冒泡/快速/归并/计数排序 && 排序原理 && 搜索树原理 && 哈希概念

    第 1 题(编程题) 题目名称: 插入排序和希尔排序 题目内容: 第 2 题(编程题) 题目名称: 选择排序和堆排序 题目内容: 第 3 题(编程题) 题目名称: 冒泡排序和快速排序 题目内容: 第 1 题(单选题) 题目名称: 2.使用选择排序对长度为100的数组进行排序,则

    2024年02月07日
    浏览(54)
  • 排序算法汇总

    https://blog.csdn.net/weixin_30342639/article/details/105343780 #include #include #include #include using namespace std; // https://blog.csdn.net/weixin_30342639/article/details/105343780 1、选择排序- 不稳定! 2、冒泡排序-稳定 3、插入排序-稳定 4、快排 5、堆排 6、归并排序–稳定 (稳定的只有插入、冒泡、归并)

    2024年02月12日
    浏览(32)
  • 【算法】排序——选择排序和交换排序(快速排序)

     ========================================================================= 主页点击直达: 个人主页 我的小仓库: 代码仓库 C语言偷着笑: C语言专栏 数据结构挨打小记:初阶数据结构专栏 Linux被操作记:Linux专栏 LeetCode刷题掉发记:LeetCode刷题 算法头疼记:算法专栏  =========================

    2024年02月08日
    浏览(46)
  • 【数据结构与算法】排序算法(选择排序,冒泡排序,插入排序,希尔排序)

    基本概念这了就不浪费时间解释了,这四种都是很简单的排序方式,本专栏后续文章会出归并排序,计数排序,快速排序,堆排序,桶排序等排序算法,今天这篇文章中给出选择排序,冒泡排序,插入排序和希尔排序的实现; 如果发现文章中有错误,还请大家指出来,我会非

    2024年02月15日
    浏览(86)
  • 排序算法(一) -- 选择排序和冒泡排序

    选择排序和冒泡排序是我们初学C语言必学的两种简单的排序算法,也是我们以后学习数据结构与算法课程中更复杂的排序算法的基础。本文用由浅入深的逻辑条理,试图将这两种排序算法讲解清楚。 本文所有的排序均是针对一维数组的,全文所用的一维数组的例子如下: 一

    2024年02月06日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包