数据结构与排序算法学习笔记

一、堆排序详解

1. 什么是堆（Heap）

堆是计算机科学中的一种特殊数据结构，它可以被视为一棵完全二叉树的数组表示形式。根据节点与父节点的大小关系，堆分为两类：

大顶堆（大根堆）：任意一个节点总是不大于其父节点（即父节点的值 ≥ 子节点的值）。
小顶堆（小根堆）：任意一个节点总是不小于其父节点（即父节点的值 ≤ 子节点的值）。

2. 完全二叉树与满二叉树

完全二叉树：满二叉树的最后一层节点可以不满，但是必须靠左紧密排列。
满二叉树：除叶子节点之外，其余所有节点的度都为 2（即每个非叶子节点都有两个子节点）。

3. 二叉树核心性质公式

在堆排序的数组映射中，以下性质至关重要：

二叉树第 i 层上的节点数目最多为 2^(i-1)。
树高为 i 的总节点数最多为 2^i - 1。
包含 n 个节点的树，其树高最少为 log₂(n+1)。
度为 2 的节点数 + 1 = 叶子节点数。

4. 堆排序四步流程详解

堆排序的核心思想是利用大顶堆（或小顶堆）的特性，反复提取极值。以升序排列为例，流程如下：

建堆：将无序数组调整为大顶堆。对于 n 个元素，从最后一个非叶子节点（索引为 n/2 - 1）开始，自底向上、自右向左进行下沉调整。例如 11 个元素从索引 5 开始调整，10 个元素同理从索引 4 开始。
交换：将堆顶元素（当前最大值）与数组最后一个元素交换，此时最大值归位。
恢复堆：将剩余 n-1 个节点重新调整为大顶堆（仅对堆顶进行下沉调整）。
重复：重复步骤 2 和 3，直到所有元素有序。

二、堆排序完整 Java 实现

以下是堆排序的完整 Java 代码，包含了建堆、调整堆和交换操作，并附有详细注释：

public class HeapSort {

    /**
     * 堆排序主方法
     * @param arr 待排序数组
     */
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        // 1. 建堆：从最后一个非叶子节点开始，自底向上调整
        // 最后一个非叶子节点索引为 arr.length / 2 - 1
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        
        // 2. 排序：依次将堆顶元素与末尾元素交换，并重新调整堆
        for (int i = arr.length - 1; i > 0; i--) {
            // 将堆顶元素（最大值）与当前末尾元素交换
            swap(arr, 0, i);
            // 对剩余的 i 个元素重新调整为大顶堆
            adjustHeap(arr, 0, i);
        }
    }

    /**
     * 调整堆（下沉操作），将指定节点调整为大顶堆
     * @param arr 数组
     * @param index 当前需要调整的节点索引
     * @param length 堆的有效长度
     */
    private static void adjustHeap(int[] arr, int index, int length) {
        int temp = arr[index]; // 暂存当前节点的值
        // 从当前节点的左子节点开始遍历 (左子节点索引 = 2 * index + 1)
        for (int k = 2 * index + 1; k < length; k = 2 * k + 1) {
            // 如果右子节点存在且大于左子节点，则指向右子节点
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;
            }
            // 如果子节点大于父节点，将子节点的值赋给父节点
            if (arr[k] > temp) {
                arr[index] = arr[k];
                index = k; // 继续向下调整
            } else {
                break; // 当前节点已满足大顶堆性质，退出循环
            }
        }
        // 将暂存的值放入最终位置
        arr[index] = temp;
    }

    /**
     * 交换数组中两个位置的元素
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

三、桶排序与分治思想详解

1. 核心思想

桶排序（Bucket Sort）是分治思想在排序算法中的典型应用。其核心逻辑是将数据分为几个部分，分别处理后再合并。

2. 执行流程

分桶：将待排序数据按照一定的规则（如数值范围）分配到有限数量的"桶"中。
桶内排序：对每个非空桶内的数据进行排序（可以使用其他排序算法或递归使用桶排序）。
合并：按照桶的顺序，依次将各个桶中的元素取出，拼接成最终的有序序列。

3. 适用场景

桶排序的时间复杂度在理想情况下可以达到 O(n+k)，但它高度依赖于数据的分布特征。当数据均匀分布在某个区间内时，桶排序效率极高；若数据分布极度不均，退化为普通比较排序。

四、插入排序 Java 实现与解析

1. 完整代码

package cn.wolfcode.domain;

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {-1, 2, 9, 8, 2, 4, 3, 5, 2, 0, 5};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 插入排序核心逻辑
     */
    private static void sort(int[] arr) {
        // 外层循环：从第二个元素开始，逐个将元素插入到前面已排序的序列中
        for (int i = 0; i < arr.length; i++) {
            // 内层循环：将当前元素 arr[i] 与前面的元素依次比较并交换
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    swap(arr, j, j - 1);
                }
            }
        }
    }

    /**
     * 交换数组中指定位置的两个元素
     */
    private static void swap(int[] arr, int i, int maxPostion) {
        int temp = arr[i];
        arr[i] = arr[maxPostion];
        arr[maxPostion] = temp;
    }
}

2. 逐行解析

for (int i = 0; i < arr.length; i++)：外层循环遍历整个数组。虽然插入排序通常从索引 1 开始，但此处从 0 开始，当 i=0 时内层循环条件 j > 0 不成立，直接跳过，不影响逻辑正确性。
for (int j = i; j > 0; j--)：内层循环负责"插入"动作。从当前元素位置 i 开始，不断向前比较。
if (arr[j] < arr[j - 1])：如果当前元素小于前一个元素，说明顺序不对，需要交换。
swap(arr, j, j - 1)：执行交换操作，将较小的元素向前挪动一位。当遇到 arr[j] >= arr[j-1] 时，内层循环继续但不再交换，直到 j=0 退出，完成本次插入。

五、排序算法总结对照表

算法名称	核心思想	时间复杂度（平均）	空间复杂度	稳定性	备注
堆排序	利用大顶堆/小顶堆特性，反复提取极值	O(n log n)	O(1)	不稳定	原地排序，建堆从最后一个非叶子节点开始
桶排序	分治思想，分桶、桶内排序、合并	O(n + k)	O(n + k)	稳定	适合数据分布均匀的场景，非比较排序
插入排序	将未排序元素插入到已排序序列的正确位置	O(n²)	O(1)	稳定	适合小规模或基本有序的数据，通过相邻交换实现