Python | 11大排序学习总结
2025.7.12-7.13简介此文章是本人对11大排序的学习和理解方便自己以后回想记忆。好了正片开始11.选择排序特点一个对小白友好的排序理解从未排序序列中选择出最小元素排在第一位。此后依此循环直到序列呈升序排列算法结束。eg序列 8 5 6 4 3 7 102①最小元素为2把它排在第一位28 5 6 437 10②2不动剩下序列中第二小元素为3把它排在第二位238 5 647 10③2 3不动再排第三小元素4把它放在第三位2 348 5 6 7 10用Python实现此排序我这个打印出来是递减排序。若升序则将 改为即可。代码解释Q1时间复杂度 O(n^2Q2空间复杂度 O(n^2)Q3: 改善时间复杂度用线段树优化选择最值过程10.冒泡排序特点气泡数值小逐渐浮出水面理解比较相邻的元素数值大的元素不断到达序列末尾。eg85 6 4 3 7 10 2①8 VS 585 则8向后移动1位 (586 4 3 7 10 2)②8 VS 686 (5 684 3 7 10 2)③8 VS 484 (5 6 483 710 2④⑤同理⑥8VS10: 810 则10向末尾移动 (5 6 4 3 782 10代码展示代码解释Q1时间复杂度 O(n^2)Q2空间复杂度 O(1)Q3如果是递增顺序就没有必要排了9.插入排序形象记忆整理扑克牌理解前一个元素和它后面相邻元素进行比较数值小的那个插入到它在此序列中真正合适的位置eg8 5 6 4 3 7 10 2①855 864 3 7 10 2②86 and 65 (56843 7 10 2)③865445 6 83 7 10 2代码展示代码解释Q1时间复杂度 O(n^2)Q2空间复杂度 O(1)8.归并排序特点用到了递归和合并理解先分后合分治思想eg8 5 6 4 3 7 10 2①分组: ( 8 5 | 6 4 | 3 7 | 10 2 )②组内排序( 5 8 | 4 6 | 3 7 | 2 10)③两两一组合并(4 5 6 8 | 2 3 7 10)④最后合并两个数组即可代码展示此处打印出来的是递减序列。 若升序把if a[l] a[r] 改为即可代码解释Q1时间复杂度 O(nlogn)Q2: 空间复杂度 O(n)Q3: 没必要的就不枚举7.桶排序理解数字们快到到桶里来桶里装的数字必须是第二桶所有数都比第一桶大后面步骤进行选择排序eg7 11 5 9 8 6 3 12 1 10 4 2①生成三个桶②放入数字(3 1 4 27 5 8 611 9 12 10代码展示代码解释6.计数排序理解类似于累计eg2 3 1 3 2 1 4 2 4 6 2①生成区间范围为19的计数器数组②数字一一放入计数器数组中图片来自b站UP主英雄哪里出来代码展示代码解释时间复杂度 O(nk)空间复杂度O(k)5.基数排序理解建立几个桶按照个 十 百 千 位依次排序每次都要取出来放回原数组中 本质也是个桶排序代码展示代码解释有负数的情况设置偏移量把所有数先减去最小的负数排序完再加上最小数时间复杂度 O(d*(nk))空间复杂度 O(nk)4.快速排序理解选择一个基准数不动让它和其他数比较大于它的数放一起 小于它的数放一起 基准数和左临界数左边的数字交换位置最后用递归排序完成eg8 5 12 9 4 10 11 3 6 7 2 1以8为基准(8 5 9 4 3 6 7 2 1 12 9 10 11)把8和1交换(1 5 9 4 3 6 7 2 8 12 9 10 11)依此循环代码展示代码解释时间复杂度O(nlogn)空间复杂度O(logn)当数列升序排列时 有局限性3.随机快速排序理解基准数随机了其他没变代码展示解释时间复杂度O(nlogn)空间复杂度O(logn)2.希尔排序插入排序进阶版eg8 5 6 4 3 7 10 2增量为四 分为四组 8 35 76 104 2)同组内部插入排序 3 85 76 102 4)增量为二 分为两组3 6 8 105 2 7 4第一组不动 第二组再进行插入排序增量为一 所有元素归一3 6 8 10 2 4 5 7 最后再进行插入排序代码展示解释时间复杂度O(n^2)空间复杂度O(11.堆排序运用完全二叉树大/小顶堆最大/小的数在最顶端结点编号idx左子数根编号idx * 2右子数根编号idx * 2 1下沉数字小的往下走eg手绘有点丑一点哈哈全部排完即形成大顶堆后要保证升序排列就把最大数与序号最大所在的数进行交换eg代码展示解释时间复杂度O(nlogn)空间复杂度O(1)反思在此学习中仍需改进地方①不会从例题的升序排列到自己操作降序排列 ②如果有负数存在像基数排列却无从下手 ③有些基础知识例如时间复杂度空间复杂度 完全二叉树尚未掌握解决方案还需要多举一反三 多尝试 学会模仿后需自行动手操作。后续会发出一篇关于时间复杂度空间复杂度 完全二叉树相关知识补充结语感谢自己最后坚持下来学完十一大排序和写完这篇文章再接再厉希望每天能敲敲代码目前熟练度也有所上升写博客其实和我初中写的那种图文文章还不太一样博客更注重事实和证明偏理那种吧学编程和写博客让我感悟到了自学要先学会模仿嗯。本次学习资料来源bilibili的UP主英雄哪里出来我看弹幕里说up主好像也有CSDN的账号不知道是不是真的非常感谢“佛祖老师”的Python课 无论是视频效果还是编程技术都很牛波一
