【java实现+4种变体完整例子】排序算法中【堆排序】的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格

以下是堆排序的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格：

一、堆排序基础实现

原理

基于二叉堆结构（最大堆），通过以下步骤实现排序：

1. 构建最大堆：将数组调整为一个最大堆，根节点为最大值。
2. 提取最大值：将堆顶元素（最大值）与末尾元素交换，缩小堆范围，重新调整堆。
3. 重复步骤2：直到堆为空。

代码示例

public class HeapSort {
    void sort(int[] arr) {
        int n = arr.length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // Extract elements one by one
        for (int i = n - 1; i >= 0; i--) {
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // Heapify the reduced heap
            heapify(arr, i, 0);
        }
    }

    // Recursive heapify to build a max heap
    private void heapify(int[] arr, int n, int i) {
        int largest = i; // Initialize largest as root
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        // If left child is larger than root
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        // If right child is larger than largest so far
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        // If largest is not root
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }
}

复杂度分析

• 时间复杂度：O(n log n)（所有情况）。
• 空间复杂度：O(log n)（递归调用栈空间）。
• 稳定性：不稳定（相同值的元素可能因交换顺序改变相对位置）。

二、常见变体及代码示例

1. 迭代实现（非递归）

改进点：用循环替代递归，减少栈空间开销。
适用场景：避免递归深度限制或优化性能。

public class IterativeHeapSort {
    void sort(int[] arr) {
        int n = arr.length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            iterativeHeapify(arr, n, i);
        }

        // Extract elements one by one
        for (int i = n - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            iterativeHeapify(arr, i, 0);
        }
    }

    // Iterative heapify to build a max heap
    private void iterativeHeapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        while (true) {
            if (left < n && arr[left] > arr[largest]) {
                largest = left;
            }
            if (right < n && arr[right] > arr[largest]) {
                largest = right;
            }
            if (largest == i) break;

            // Swap and continue
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            i = largest;
            left = 2 * i + 1;
            right = 2 * i + 2;
        }
    }
}

2. 最小堆实现

改进点：使用最小堆实现排序，需反转结果。
适用场景：需用最小堆结构的场景（如优先队列）。

public class MinHeapSort {
    void sort(int[] arr) {
        int n = arr.length;

        // Build min heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // Extract elements one by one (ascending order requires reversal)
        for (int i = n - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            heapify(arr, i, 0);
        }
        reverse(arr); // Reverse to get ascending order
    }

    // Heapify for min heap
    private void heapify(int[] arr, int n, int i) {
        int smallest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] < arr[smallest]) {
            smallest = left;
        }
        if (right < n && arr[right] < arr[smallest]) {
            smallest = right;
        }
        if (smallest != i) {
            swap(arr, i, smallest);
            heapify(arr, n, smallest);
        }
    }

    private void reverse(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            swap(arr, left, right);
            left++;
            right--;
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

3. 原地堆排序优化

改进点：减少比较次数，优化堆调整过程。
适用场景：追求极致性能的场景。

public class OptimizedHeapSort {
    void sort(int[] arr) {
        int n = arr.length;

        // Build max heap with reduced comparisons
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // Extract elements one by one
        for (int i = n - 1; i >= 0; i--) {
            swap(arr, 0, i);
            heapify(arr, i, 0);
        }
    }

    // Optimized heapify to reduce comparisons
    private void heapify(int[] arr, int n, int i) {
        while (true) {
            int largest = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            if (left < n && arr[left] > arr[largest]) {
                largest = left;
            }
            if (right < n && arr[right] > arr[largest]) {
                largest = right;
            }

            if (largest == i) break;

            swap(arr, i, largest);
            i = largest;
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

三、变体对比表格

四、关键选择原则

1. 基础场景：优先使用基础递归实现，因其简单易懂。
2. 栈限制场景：迭代实现适合避免递归深度限制（如超大数组）。
3. 最小堆需求：最小堆变体适用于需要最小堆结构的场景，但需额外反转步骤。
4. 性能优化：原地优化版通过减少比较次数提升效率，适合对性能敏感的场景。
5. 稳定性需求：所有变体均不稳定，若需稳定排序需选择其他算法（如归并排序）。

通过选择合适的变体，可在特定场景下优化性能或适应硬件限制。例如，迭代实现避免栈溢出，而原地优化版通过减少比较次数提升效率。