DS-排序回顾

---

快速排序相比于堆排序的优点有：

1. 效率更高：快速排序的平均时间复杂度为 O(nlogn)，而堆排序的时间复杂度为 O(nlogn)。虽然它们的时间复杂度相同，但是在实际情况下，快速排序往往比堆排序更快，因为快速排序具有良好的局部性和缓存性能。

2. 原地排序：快速排序是一种原地排序算法，它不需要额外的空间来存储临时数据。相比之下，堆排序需要使用额外的空间来构建和维护堆。
   快速排序需的递归栈深度=O(n)，平均O(log₂n)，堆排序构建和维护栈不要额外空间

3. 稳定性：快速排序是一种不稳定的排序算法，意味着相等元素的相对顺序可能会发生改变。而堆排序是一种稳定的排序算法，相等元素的相对顺序不会改变。

4. 对于小规模数据集的处理更快：当待排序的数据规模较小时，快速排序通常比堆排序更快。这是因为快速排序在每次递归时只需要处理部分数据，而堆排序需要对整个数据集进行操作。

总体而言，快速排序在大多数情况下更加高效且具有更好的性能表现，但在某些特殊情况下，堆排序可能更适合使用。

---

插入排序系

1. 插入排序，每次查找未排序记录的第一个在已排序记录中的位置，比较的过程中将大者后移一位
2. 希尔排序，间隔从大到小，每次用插入排序
3. 折半查找，每次找到位置，什么时候更新？

选择排序

1. 本体：每次从未排序中选最小的放在前面
2. 堆排序：——optimal applied situation/scene：1亿个只取100个最大的
   构建initial堆：
3. 按插入，最小堆的构建O(n)
4. 筛选法：从$\lceil$ n/2 $\rceil$ 的位置开始，将该节点(以最小堆为例)下移到左右子均比它大，用时最坏O(n)，最好(n/2)，平均O(n)
   排序：每次将堆顶与堆尾交换，再下移新堆顶，用时O(nlog2n)，
   1+2总用时O(nlogn)
   插入：放到堆尾，上移到比双亲大
   删除：与堆尾交换，原堆尾再下移到比孩子小，删除新的堆尾

交换排序

1. 冒泡排序：从后往前，每次把最小的放到最前边
2. 快速排序：任取一点(队首)，分治法，左边为小的，右边为大的，逆序对交换，递归层数=(log₂n - n)

归并和基数

1. 归并：与希尔的共同点，都有一个超参幂乘

• 2路归并：归并段直接比较即可，不同归并段的合并用额外空间，比较次数n_2n-1，log2_{n次归并O(nlog}2~n)
• k路平衡归并：败者树，初始二叉树用时k-1，有序归并段中取出新的最小值用时O(log₂k)，一趟合并用时O(nlog₂k)，共O(nlog₂k log~k n)=O(nlog₂n)，初始归并段的获得，可用快排平均O(nlog₂k)，最坏O(n²)（置换-选择得到的为非平衡，败者树用时O(nlog₂|WA|)）

2. 基数排序：按位数从小到大，用计数排序
   计数排序可用1）数组形式，~~2）每个数据需要包含一个指针，r个队列(数据数位0-r-1)，存储当次排序的首指针？~~算了我们还是用标准的数组把

外部排序

1. 数据量太大，内存放不下，一般采用归并方法，每次取一小段，排好了再放回去
2. 对m路归并，内存缓冲区分成2m个输入区和2个输出区(存放归并完成的结果)，*2=1个存放内存到缓冲区的交互，一个用于中和缓冲区和外存的交互
   缓冲区1写满了，就全部放到buffer2，接着往buf1写，同时buf2并行写入memory
3. 如何减小归并趟数，进而减小访存次数？

• 增大归并的路数，但直接比较来确定r个有序队列最小值，导致比较用时上升；采用败者树可以抵消路数增大导致的比较时间变长
• 增大初始段长，置换-选择法，将初始序列通过k=|WA|的败者树分成不定长有序初始段的集合，段长即为为归并代价
  —— 利用Huffman算法，得到合并路径的规划方案，k路不平衡归并总用时=2*WPL*log₂k O(WPL*log₂k)