数据结构笔记-排序部分。

排序

排序算法是计算机科学中用于对元素序列进行排序的一系列方法。

稳定排序：若排序后，相同关键字的记录保持它们原来的相对次序，则此排序方法称为稳定排序。

不稳定排序：若排序后，相同关键字的记录不能保持它们原来的相对次序，则此排序方法称为不稳定排序。

排序类型：

内部排序：全部数据存于内存。
外部排序：需要对外存进行访问的排序过程。

插入排序

直接插入排序

概念：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。过程：

对 $ R_1, \ldots, R_{i-1} $ 已排好序，有 $ K_1 \leq K_2 \leq \ldots \leq K_{i-1} $。
现将 $ K_i $ 依次与 $ K_{i-1}, K_{i-2}, \ldots $ 进行比较，并移动元素，直到发现 $ Ri $ 应插在 $ R_j $ 与 $ R_{j+1} $ 之间（即有 $ K_j \leq K_i \leq K_{j+1} $），则将 $ Ri $ 插到 $ j + 1 $ 号位置上，形成 $ i $ 个有序序列。 $ (i $ 从 2 到 $ n) $。

算法分析：

空间复杂度：$ O(1) $
时间复杂度：$ O(n^2) $
稳定性：稳定排序。

折半插入排序算法

折半插入排序是直接插入排序的一种优化。

概念：在插入元素前，使用折半查找法确定插入位置。
时间复杂度：平均和最坏情况为O(n^2)，最好情况为O(nlogn)。

2-路插入排序算法

2-路插入排序是直接插入排序的一种优化。

概念：通过引入一个辅助数组来减少排序过程中的数据移动次数，‌从而提高排序效率。在排序过程中，‌对于待排序的每个元素，‌根据其大小将其插入到辅助数组中的正确位置，‌而不是像传统插入排序那样逐个比较和移动元素。‌
时间复杂度：平均和最坏情况为O(n^2)。

希尔排序算法

概念：是插入排序的一种更高效的改进版本，通过引入增量来对元素进行分组，然后对每组进行插入排序。过程：
1. 先确定一个初始的增量（需要根据数组的特点进行选择以提高希尔排序的效率）。
2. 将数组分为若干个子序列。
3. 对这若干个子序列进行插入排序。
4. 递减初始增量，并重复操作2和3，直至增量为1。‌
时间复杂度：平均为O(n^1.3)，最坏为O(n^2)。

交换排序

冒泡排序

概念：通过重复遍历要排序的数列，比较每对相邻元素的大小，并在必要时交换它们的位置。

基本思想：通过多次重复比较、交换相邻记录而实现排序；每一趟的效果都是将当前键值最大的记录换到最后。

算法分析：

时间复杂度：$ O(n^2) $
空间复杂度：$ O(1) $
稳定性：稳定排序。

快速排序

概念：通过选取一个“基准”元素，将数列分为两部分，一部分包含所有小于基准的元素，另一部分包含所有大于基准的元素，然后递归地在这两部分上重复这个过程。

基本思想：通过分步排序完成整个表的排序；首先取第一个记录，将之与表中其余记录比较并交换，从而将它放到记录的正确的最终位置。使记录表分成两部分：其一（左边的）诸记录的关键字均小于它；其二（右边的）诸记录的关键字均大于它。然后对这两部分重新执行上述过程，依此类推，直至排序完毕。

算法分析：

空间复杂度：$ O(\log n) $
时间复杂度：$ O(n \log n) $（平均情况），$ O(n^2) $（最坏情况）
稳定性：不稳定排序。

选择排序

直接选择排序

概念：在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。

过程：设记录 $ R_1, R_2, \ldots, R_n $，对 $ i = 1, 2, \ldots, n-1 $ 重复下列工作：

在 $ R_i, \ldots, R_n $ 中选最小（或最大）关键字记录 $ R_j $；
将 $ R_j $ 与第 $ i $ 个记录交换位置，即将选到的第 $ i $ 小的记录换到第 $ i $ 号位置上。

算法分析：

空间复杂度：$ O(1) $
时间复杂度：$ O(n^2) $
稳定性：不稳定排序。

堆排序

概念：利用堆这种数据结构所设计的一种排序算法，堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。

堆的定义：集合 $ {K_1, K_2, \ldots, K_n} $，对所有 $ i = 1, 2, \ldots, n/2 $ 有：

$ K_i \leq K_{2i} $ 且 $ K_i \leq K_{2i+1} $（最小堆）；
$ K_i \geq K_{2i} $ 且 $ K_i \geq K_{2i+1} $（最大堆）。

建堆（筛选法）：

顺序输入成完全二叉树（以数组存储）。
从最后一个双亲开始，如果有较小的孩子，则将其沿左或右孩中小的那个方向筛下，一直到不能再筛。
逐次处理完每个双亲。

堆排序过程：

从 $ i = \lfloor n / 2 \rfloor - 1 $ 调用 $ sift(r, i, n) $ 建初始堆。
对 $ i = n, n - 1, n - 2, \ldots, 2 $ 重复以下步骤：
- 输出 $ r[1] $，即 $ r[1] \leftarrow r[i] $。
- 调用 $ sift(r, 1, i - 1) $，重新建堆。

算法分析：

空间复杂度：$ O(1) $
时间复杂度：\

归并排序

归并排序是一种基于比较的排序算法，采用分治法的策略。它将数组分成两半，递归地对每一半进行排序，然后将两个有序的部分合并成一个有序的整体。

关键步骤：

分解： 将数组不断拆分为更小的子数组，直到每个子数组只有一个元素。这是因为单个元素自然视为已排序。
合并： 从最底层开始，递归地将相邻的子数组合并为一个有序数组。合并过程中，两个有序数组中的元素按顺序逐个比较，较小的元素先放入结果数组中。

算法流程

如果数组长度小于等于1，直接返回该数组。
找到数组的中间位置，将数组分为左右两部分。
对左半部分和右半部分分别进行归并排序。
合并两个已排序的子数组。

算法分析

时间复杂度：O(n log n)，无论最好、最坏或平均情况都是如此。
空间复杂度：O(n)，因为需要额外的空间来存储临时数组用于合并操作。

桶排序

桶排序是一种分布式的排序算法，它假设输入数据是均匀分布的。它通过将数据分布到一系列“桶”中，然后对每个桶中的数据进行排序，最后将桶中的数据合并以得到最终排序的结果。

桶：桶是用于暂时存放数据的容器，每个桶代表数据的一个区间。
均匀分布： 桶排序假设输入数据是均匀分布的，这有助于数据在各个桶之间均衡分配。

算法流程

初始化： 根据输入数据的分布特性，创建一定数量的空桶。
分配： 将输入数据中的每个元素分配到相应的桶中。通常，使用一个函数（如比例函数）来确定元素应该放入哪个桶。
排序： 对每个桶内的数据进行排序，通常可以使用其他更高效的排序算法，如插入排序或归并排序。
收集： 按照桶的顺序收集所有桶中的元素，形成排序后的数组。

算法分析：

时间复杂度：在理想情况下，如果输入数据是均匀分布的，桶排序的时间复杂度可以达到O(n + k)，其中n是元素数量，k是桶的数量。但在最坏情况下，如果所有的数据都集中在一个桶内，时间复杂度会退化为O(n^2)。
空间复杂度：O(n+k)，需要额外的空间来存放桶和桶中的数据。

基数排序

基数排序是一种桶排序。

基数排序是一种非比较型整数排序算法，其原理是按照低位先排序，然后收集；再按高位排序，然后再收集；依次类推，直到最高位。基数排序属于稳定排序，常用于处理大量整数的排序。

基数： 基数排序中的“基数”指的是数字系统中的基数，例如十进制系统中的基数是10。

算法流程

初始化： 设定最大数的位数，创建与基数相同数量的空“桶”。
分配： 从最低有效位（个位）开始，将所有待排序的数分配到对应的桶中。
收集： 按照桶的顺序收集桶中的元素，形成一个新的序列。
重复： 对新序列重复步骤2和3，每次处理下一位，直到处理完最高位。

算法分析

时间复杂度：O(d*(n+b))，其中d是最大数的位数，n是待排序元素的数量，b是基数。在固定基数和位数的情况下，基数排序的时间复杂度接近线性。
空间复杂度：O(n+b)，需要额外的空间存放桶和输出数组。

总结

排序算法的选择依赖于数据的特性和排序的规模。

对于小规模数据，简单排序算法如插入排序或冒泡排序可能足够高效。对于大规模数据，更高效的算法如快速排序、归并排序或基数排序通常是更好的选择。