大家好，我是童磨，对，就是你们的万世极乐教教主，今天不吃人，来讨论一下算法。
前情提要：
自从在无限城和鬼杀队打输了之后，无惨大人一气不打处来…
咳咳，
切入正题，我们今天来讲排序。
一、时间复杂度
学排序之前要先知道时间复杂度是什么：
算法的时间复杂度是指算法执行过程中所需要的基本运算次数，用于定性描述算法运行时间随输入规模增长的变化规律 。它不是具体的物理执行时间，而是衡量算法效率的理论指标，关注输入规模 nn 趋向无穷大时的渐进表现 。
二、选择排序和冒泡排序
选择排序和冒泡排序是两种基础的排序算法，均属于比较类排序，时间复杂度均为 O(n²)，适用于小规模数据或教学演示。
1.冒泡排序
-
基本思想：重复遍历待排序数组，依次比较相邻元素，若顺序错误（如前大于后）则交换，每轮遍历会将当前未排序部分的最大值“冒泡”到末尾。
-
关键特点：
1> 每轮最多交换 n−1 次；
2>可通过设置标志位优化：若某轮无交换，说明已有序，可提前终止；
3> 是稳定排序（相等元素相对位置不变）；
4> 原地排序，空间复杂度为O(1)。
2.选择排序 -
基本思想：每轮从未排序部分中找出最小（或最大）元素，将其与未排序部分的第一个元素交换，从而逐步扩大已排序区域。
-
关键特点：
1> 每轮只交换一次（即使最小值已在首位）；
2> 不稳定排序（相同元素可能因交换改变相对位置）；
3> 时间复杂度恒为 O(n²)，无论数据是否有序；
4> 原地排序，空间复杂度为 **O(1)**。
三、桶排序
1.桶排序
桶排序是一种基于分治思想的非比较型排序算法，适用于待排序数据均匀分布在某个范围内的场景。其核心思想是将数据分配到有限数量的“桶”中，对每个桶单独排序，最后按顺序合并所有桶中的元素，得到最终有序序列。
核心原理
- 设置桶的数量与范围：根据输入数据的最小值、最大值及分布特性，确定桶的数量 mm 和每个桶覆盖的值区间。
- 元素分配：遍历待排序数组，将每个元素通过映射函数（如
index=⌊(x−min)×m/(max−min)⌋index=⌊(x−min)×m/(max−min)⌋）分配到对应桶中。 - 桶内排序：对每个非空桶中的元素使用其他排序算法（如插入排序、快速排序等）进行排序。
- 合并结果：按桶的顺序依次取出所有元素，拼接成最终有序数组。
好，这节课就讲到这里，下节课我们讲sort排序。
下课！
（本蒟蒻第一次写课程，大佬们有建议麻烦提一提）
