2025.7.12-7.13

简介：

  此文章是本人对11大排序的学习和理解，方便自己以后回想记忆。好了正片开始！

---

11.选择排序

特点：一个对小白友好的排序

理解：从未排序序列中，选择出最小元素排在第一位。此后依此循环，直到序列呈升序排列，算法结束。

eg：序列 （8 5 6 4 3 7 10 2）

       ①最小元素为2，把它排在第一位

          （2 8 5 6 4 3 7 10）

      ②2不动，剩下序列中第二小元素为3，把它排在第二位（2 3 8 5 6 4 7 10）

      ③2 3不动，再排第三小元素4，把它放在第三位（2 3 4 8 5 6 7 10）

用Python实现此排序：

（我这个打印出来是递减排序。若升序，则将> 改为<＝即可。）

代码解释：

Q1：时间复杂度 O(n^2）

Q2：空间复杂度 O(n^2)

Q3: 改善时间复杂度：用线段树优化选择最值过程

---

10.冒泡排序

特点：气泡（数值小）逐渐浮出水面

理解：比较相邻的元素，数值大的元素不断到达序列末尾。

eg：（8 5 6 4 3 7 10 2）

         ①8 VS 5：8>5 则8向后移动1位                                        (5 8 6 4 3 7 10 2)

         ②8 VS 6：8>6 (5 6 8 4 3 7 10 2)

         ③8 VS 4：8>4 (5 6 4 8 3 7 10 2）

         ④⑤同理

         ⑥8VS10: 8<10 则10向末尾移动                                      (5 6 4 3 7 8 2 10）

代码展示：

代码解释：

Q1：时间复杂度 O(n^2)

Q2：空间复杂度 O(1)

Q3：如果是递增顺序，就没有必要排了

---

9.插入排序

形象记忆：整理扑克牌

理解：前一个元素和它后面相邻元素进行比较，数值小的那个插入到它在此序列中真正合适的位置

eg：（8 5 6 4 3 7 10 2）

      ①8>5（5 8 6 4 3 7 10 2）

      ②8>6 and 6>5  (5 6 8 4 3 7 10 2)

      ③8>6>5>4（4 5 6 8 3 7 10 2）

代码展示：

代码解释：

 

Q1：时间复杂度 O(n^2)

Q2：空间复杂度 O(1)

---

8.归并排序

特点：用到了递归和合并

理解：先分后合，分治思想

eg：（8 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.桶排序

理解：数字们快到到桶里来！桶里装的数字必须是第二桶所有数都比第一桶大，后面步骤进行选择排序

eg：（7 11 5 9 8 6 3 12 1 10 4 2）

①生成三个桶（［］［］［］）

②放入数字(［3 1 4 2］［7 5 8 6］［11 9 12 10］

代码展示：

 

代码解释：

---

6.计数排序

理解：类似于累计

eg：（2 3 1 3 2 1 4 2 4 6 2）

①生成区间范围为［1，9］的计数器数组

 ②数字一一放入计数器数组中：

 （图片来自b站UP主：英雄哪里出来）

代码展示：

代码解释：

时间复杂度： O(n+k) 

空间复杂度：O(k) 

---

5.基数排序

理解：建立几个桶，按照个 十 百 千 位依次排序，每次都要取出来放回原数组中 本质也是个桶排序

代码展示：

代码解释：

 有负数的情况：设置偏移量（把所有数先减去最小的负数排序完，再加上最小数）

时间复杂度： O(d*(n+k))

空间复杂度： O(n+k)

---

4.快速排序

理解：选择一个基准数（不动），让它和其他数比较，大于它的数放一起 小于它的数放一起 基准数和左临界数左边的数字交换位置，最后用递归排序完成

eg：（8 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.希尔排序（插入排序进阶版）

eg：（8 5 6 4 3 7 10 2）

增量为四 分为四组：（ ［8 3］［5 7］［6 10］［4 2］)

同组内部插入排序：（ ［3 8］［5 7］［6 10］［2 4］)

增量为二 分为两组：（［3 6 8 10］［5 2 7 4］）

第一组不动 第二组再进行插入排序

增量为一 所有元素归一：（3 6 8 10 2 4 5 7 ）

最后再进行插入排序

代码展示+解释：

 时间复杂度：O(n^2)

空间复杂度：O(1）

---

1.堆排序（运用完全二叉树）

大/小顶堆：最大/小的数在最顶端

结点编号：idx

左子数根编号：idx * 2

右子数根编号：idx * 2 + 1

下沉：数字小的往下走 

eg

 （手绘有点丑一点哈哈）

全部排完（即形成大顶堆）后要保证升序排列，就把最大数与序号最大所在的数进行交换

eg：

 代码展示+解释：

时间复杂度：O(nlogn)

空间复杂度：O(1)

---

反思：

  在此学习中，仍需改进地方：①不会从例题的升序排列到自己操作降序排列 ②如果有负数存在（像基数排列）却无从下手 ③有些基础知识（例如时间复杂度，空间复杂度 完全二叉树）尚未掌握 

解决方案：还需要多举一反三 多尝试 学会模仿后需自行动手操作。后续会发出一篇关于时间复杂度，空间复杂度 完全二叉树相关知识补充

---

结语：

感谢自己最后坚持下来学完十一大排序和写完这篇文章！再接再厉，希望每天能敲敲代码，（目前熟练度也有所上升）

写博客其实和我初中写的那种图文文章还不太一样，博客更注重事实和证明（偏理那种吧）

学编程和写博客让我感悟到了自学要先学会模仿，嗯。

---

本次学习资料来源：

bilibili的UP主：英雄哪里出来

（我看弹幕里说up主好像也有CSDN的账号，不知道是不是真的）

非常感谢“佛祖老师”的Python课 无论是视频效果还是编程技术都很牛波一