感谢您的要求！以下是将之前的Markdown笔记翻译成中文的版本，内容保持一致，格式遵循您提供的Markdown标准（嵌套列表缩进四格、列表下数学公式缩进四格且前后空行、列表与前后文字空行）。笔记从学生视角编写，涵盖PPT“DS12_Ch06_Shellsort_Heapsort_MergeSort (1).ppt”的所有知识点，风格参考Lecture7和Lecture8。

DS12 第6章：希尔排序、堆排序和归并排序

本笔记涵盖了第6章的三个排序算法：希尔排序、堆排序和归并排序。我将从学生的角度，详细分解每个算法的概念、过程、代码示例和分析，就像课堂上记笔记一样！

1. 希尔排序

1.1 基本概念

发明者：唐纳德·希尔（Donald Shell）
核心思想：希尔排序不一次性对整个数组排序，而是通过一系列增量序列（间隔）进行多轮“增量排序”，使数组逐渐趋向有序，直到完全排序。
增量序列：一个递减序列 \( h_1 < h_2 < \dots < h_t \)，其中 \( h_1 = 1 \)。每个 \( h_k \) 定义了将数组分割成子序列的间隔。

1.2 希尔排序的工作原理

hk-排序：在每个阶段，对于给定的增量 \( h_k \)：
- 将数组分割成间隔为 \( h_k \) 的子序列。
- 对每个子序列执行插入排序。
关键性质：如果数组是 \( h_k \)-排序的，则在执行 \( h_{k-1} \)-排序后仍保持 \( h_k \)-排序。
PPT中的示例：
- 初始数组：[81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15]
- 5-排序：对相隔5个位置的元素排序（例如 [81, 35]、[94, 17] 等）。
- 3-排序：然后对相隔3个位置的元素排序。
- 1-排序：最后执行常规插入排序（间隔 = 1）。

1.3 希尔的增量序列

定义：
- 从 \( h_t = \lfloor N / 2 \rfloor \) 开始。
- 下一个增量：\( h_k = \lfloor h_{k+1} / 2 \rfloor \)。
\[ h_t = \lfloor N / 2 \rfloor, \quad h_k = \lfloor h_{k+1} / 2 \rfloor \]

代码示例：

void Shellsort(ElementType A[], int N) {
    int i, j, Increment;
    ElementType Tmp;
    for (Increment = N / 2; Increment > 0; Increment /= 2) {
        for (i = Increment; i < N; i++) {
            Tmp = A[i];
            for (j = i; j >= Increment; j -= Increment) {
                if (Tmp < A[j - Increment]) {
                    A[j] = A[j - Increment];
                } else {
                    break;
                }
            }
            A[j] = Tmp;
        }
    }
}

最坏时间复杂度：\( \Theta(N^2) \)
最坏情况示例：
- 数组：[1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7, 15, 8, 16]
- 步骤：8-排序 → 4-排序 → 2-排序 → 1-排序
- 问题：增量对（例如8和4）不一定是互质的，因此较小的增量可能效果有限，导致比较和交换次数多。

1.4 其他增量序列

希巴德序列：\( h_k = 2^k - 1 \)（例如 1, 3, 7, 15, …）
- 连续增量之间没有公因数。
- 最坏情况：\( \Theta(N^{3/2}) \)
- 平均情况：\( O(N^{5/4}) \)
\[ h_k = 2^k - 1 \]
塞奇威克序列：{1, 5, 19, 41, 109, …}
- 公式：\( 9 \times 4^i - 9 \times 2^i + 1 \) 或 \( 4^i - 3 \times 2^i + 1 \)
- 平均情况：\( O(N^{7/6}) \)
- 最坏情况：\( O(N^{4/3}) \)
\[ h_i = 9 \times 4^i - 9 \times 2^i + 1 \quad \text{或} \quad 4^i - 3 \times 2^i + 1 \]
总结：希尔排序实现简单但分析复杂，适合中等规模数据集（例如数万元素）。

2. 堆排序

2.1 基本概念

核心思想：利用堆（一个父节点大于/小于子节点的完全二叉树）对数组进行排序。
堆的定义：
- 最大堆：父节点 > 子节点
- 最小堆：父节点 < 子节点
我们将聚焦于最大堆，用于升序排序。

2.2 算法1：使用额外空间的堆排序

步骤：
- 构建堆：从数组构造堆，复杂度为 \( O(N) \)。
- 删除最大值：移除最大元素（根节点） \( N \) 次，每次 \( O(\log N) \)，并存储到临时数组。
- 将临时数组复制回原数组。
时间复杂度：\( O(N \log N) \)
缺点：需要 \( O(N) \) 的额外空间用于临时数组。

2.3 算法2：原地堆排序

代码示例：

void Heapsort(ElementType A[], int N) {
    int i;
    for (i = N / 2; i >= 0; i--) { /* 构建堆 */
        PercDown(A, i, N);
    }
    for (i = N - 1; i > 0; i--) { /* 删除最大值 */
        Swap(&A[0], &A[i]);
        PercDown(A, 0, i);
    }
}

过程：
- 通过对所有非叶节点调用 PercDown（下滤）构建最大堆。
- 重复以下步骤：
  - 将根节点（最大元素）与最后一个元素交换。
  - 堆大小减1，并对新根节点进行下滤。
平均比较次数：\( 2N \log N - O(N \log \log N) \)
与希尔排序的比较：堆排序复杂度稳定为 \( O(N \log N) \)，但在实践中，采用塞奇威克序列的希尔排序可能因内存操作较少而表现更好。

3. 归并排序

3.1 基本概念

核心思想：将数组递归地分成两半，分别排序，然后将它们合并成一个有序数组。
合并操作：将两个有序子数组合并成一个有序数组。

3.2 合并两个有序列表

过程：
- 使用两个指针（Aptr、Bptr）分别指向两个列表，第三个指针（Cptr）指向合并结果。
- 比较元素，将较小的复制到结果中。
时间复杂度：\( O(N) \)，其中 \( N \) 是元素总数。
示例：将 [1, 13, 24, 26] 和 [2, 15, 27, 38] 合并为 [1, 2, 13, 15, 24, 26, 27, 38]。

3.3 归并排序实现

代码示例：

void MSort(ElementType A[], ElementType TmpArray[], int Left, int Right) {
    int Center;
    if (Left < Right) {
        Center = (Left + Right) / 2;
        MSort(A, TmpArray, Left, Center);
        MSort(A, TmpArray, Center + 1, Right);
        Merge(A, TmpArray, Left, Center + 1, Right);
    }
}

void Mergesort(ElementType A[], int N) {
    ElementType *TmpArray;
    TmpArray = malloc(N * sizeof(ElementType));
    if (TmpArray != NULL) {
        MSort(A, TmpArray, 0, N - 1);
        free(TmpArray);
    } else {
        FatalError("无法分配临时数组空间！！！");
    }
}

合并函数：将两个有序子数组合并到 TmpArray，然后复制回 A。
空间复杂度：\( O(N) \)，用于临时数组。
注意：如果在每次 Merge 调用中局部声明 TmpArray，空间复杂度会增加到：

\[ O(N \log N) \]

因此我们使用单一的全局数组。

3.4 归并排序分析

递归关系：

\[ T(N) = 2T(N/2) + O(N) \]
解：

\[ T(N) = O(N \log N) \]
迭代版本：可通过自底向上的方式实现，避免递归。
优缺点：
- 优点：稳定，适合外部排序（例如磁盘上）。
- 缺点：需要额外空间，复制操作慢，不适合内部排序。