堆排序

堆排序（Heap Sort）是利用堆（Heap）这种数据结构进行选择排序的一种算法。堆是一个可以推导具有最大或最小值的树形结构，堆排序利用堆的特性进行排序。

堆排序分为两个步骤：

1. 建堆（Build Heap）：将一个无序的数组构建成一个大顶堆（Max Heap）。大顶堆的特点是父节点的值大于或等于其子节点的值。建堆的过程从数组的最后一个非叶子节点开始，依次向上调整每个节点，使其满足大顶堆的特性。

2. 排序（Sort）：重复执行以下步骤，直到堆的大小为1：

   • 将堆中的最大元素（根节点）与堆的最后一个元素交换。
   • 将堆的大小减1。
   • 对堆进行调整，使其重新成为一个大顶堆。

重复上述步骤，每次取出的都是当前堆中的最大元素，最终得到的数组就是一个有序的数组。

堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)。由于堆排序是一种不稳定的排序算法，因此在需要保持相同元素的原始顺序时应谨慎使用。

以下是堆排序的示例代码：

Java实现

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

        // 构建大顶堆
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        // 排序
        for (int i = n - 1; i >= 0; i--) {
            // 将当前堆中的最大元素与堆的最后一个元素交换
            swap(arr, 0, i);

            // 对交换后的元素进行调整，重新成为一个大顶堆
            heapify(arr, i, 0);
        }
    }

    // 调整堆，使其重新成为一个大顶堆
    static void heapify(int[] arr, int n, int i) {
        int largest = i; // 初始化largest为当前节点
        int left = 2 * i + 1; // 左子节点
        int right = 2 * i + 2; // 右子节点

        // 如果左子节点比当前节点大，则更新largest为左子节点
        if (left < n && arr[left] > arr[largest])
            largest = left;

        // 如果右子节点比当前节点大，则更新largest为右子节点
        if (right < n && arr[right] > arr[largest])
            largest = right;

        // 如果largest不是当前节点，则将largest与当前节点交换，并递归调整堆
        if (largest != i) {
            swap(arr, i, largest);

            heapify(arr, n, largest);
        }
    }

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

    // 测试
    public static void main(String[] args) {
        int[] arr = { 12, 11, 13, 5, 6, 7 };
        sort(arr);
        System.out.println("排序后的数组：");
        for (int num : arr)
            System.out.print(num + " ");
    }
}