2021.10.31学到快速排序-分割策略
基于比较的排序：假设 N是传递到我们的排序例程中的元素的个数。按照 C语言的规定，数据从位置 0 处开始。 假设 << 和 >> 运算符存在，它们可以用于将相容的序放到输入中。除赋值运算符号外，这两种运算时仅有的允许对输入数据进行的操作。
- 算法： 插入排序由 N−1 趟排序组成。对于 P = 1 趟到 P = N - 1 趟，插入排序保证从位置 0 到 位置 P 上的元素为已排序状态。 时间复杂度：o（N^2）
- 逆序： 定理1：N 个互异数的数组的平均逆序数是 N(N−1)/4 定理2：通过交换相邻元素进行排序的任何算法平均需要 Ω(N2) 时间
- 重要性质： 一个 hk 排序后的文件将保持 hk 排序性
- 算法： 又称缩小增量排序，通过比较相距一定间隔的元素来工作，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻怨怒是的最后一趟排序为止
- 增量序列： 希尔排序使用的一个序列
- hk排序： 对于任意一个 i都有 A[i]<A[i+hk]A[i]<A[i+hk]建议的序列：ht=⌊N/2⌋ht=⌊N/2⌋ 和 hk=⌊hk+1/2⌋hk=⌊hk+1/2⌋.
- 最坏情况： 时间运行：O(N^2) N 是 2 的幂，这使得除最后一个增量为 1 外所有的增量都是偶数。 给出一个数组 InputData 作为输入，它的偶数位置上有 N/2 个同是最大的数，在奇数位置上有 N/2 个同为最小的数。由于除最后一个增量外的增量都是偶数，因此，当我们进行最后一趟排序之前， N/2 个最大的元素依旧处在偶数位置上， N/2 个最小的元素依旧处在奇数位置上。于是，在最后一趟排序开始之前的第 i 个最小的数 ( i <= N/2 ) 在位置 2i - 1 处。将第 i 个元素恢复到其正确的位置上就需要在数组中移动 i - 1 个间隔
- 堆： 元素排成更典型的递增顺序，可以改变序的特性使得父节点的关键字的值大于儿子节点的关键字的值
- 算法： 建立 N 个元素的二叉堆，花费的时间为 O(N) .然后我们执行 N 次 DeleteMin 操作。按照顺序，最小的元素先离开堆。通过将这些元素记录到第二个数组中再将数组拷贝回来，我们得到了 N 个元素的排序。 这个算法的主要问题在于它额外使用了一个数组。因此存储需求增加了一倍。
- 定理： 对 N 个互异项的随机排序进行堆排序，所用的平均次数为 2NlogN−O(NlogN)
- 算法： 若将输出放到第三个表中时则该算法可以通过对输入数据一趟排序来完成。 基本的合并算法是取两个输入数组 A 和 B，一个输出数组 C ，以及三个计数器 Aptr,Bptr,Cptr.它们初始置于对应数组的开始端。A[Aptr] 和 B[Bptr] 中的较小者将被拷贝到 C 中的下一个位置，相关的计数器则向前推进一步。当两个输入表有一个用完的时候，另一个剩余部分拷贝到 C 中
- 分析： 递归方程是： T(1)=1 T(N)=2∗T(N2)+N 最终得到： T(N)=NlogN+N
- 选择枢纽元方法： 随机选取
- 三数中值分割法 一组 N 个数的中止是第 ⌊N/2⌋ 个最大的数。枢纽元最好的选择是选择数组的中值。一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元
- 算法： 1.如果数组 SS 中的元素的个数是 0 或者 1 ，则返回； 2.取 SS 中任意一个元素 vv , 称之为枢纽元(pivot); 3.将 S−{v}S−{v} ( SS 中的其他元素 ） 分成两个不相交的集合 S1={x∈S−{v}|x≤v}S1={x∈S−{v}|x≤v} 和 S2={x∈S−{v}|x≥v}S2={x∈S−{v}|x≥v} . 返回 {quicksort(S1)}{quicksort(S1)} 之后继续 {quicksort(S2)}
平均运行时间是 O(NlogN)