堆排序java实验报告

实验目的：

通过本实验，实现对堆排序算法的理解，掌握堆排序算法的原理以及实现方法，并掌握Java语言的编程技巧。

实验内容：

堆排序是一种树形选择排序方法，是对直接选择排序算法的有效改进。堆排序的基本思想是：将待排序的序列构造成一个大根堆或小根堆，堆顶元素为最大值或最小值，然后将堆顶元素与最后一个元素交换，然后把剩余的元素重新构造成堆。如此反复执行，直到排序完成。由于堆排序算法的时间复杂度为O(nlogn)，因此在大数据量的情况下，堆排序是高效的。

堆排序算法的实现主要有两个步骤：构建初始堆和堆排序。其中，构建初始堆是将待排序的序列构建成一个大根堆或小根堆的过程，堆排序是不断将堆顶元素与最后一个元素交换，并重新调整堆的过程。

以下是Java语言实现堆排序的代码：

public class HeapSort {
    public static void heapSort(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--) {
            // 将堆顶元素与最后一个元素交换
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 调整堆
            heapify(arr, i, 0);
        }
    }

    // 调整堆
    public static void heapify(int[] arr, int n, int i) {
        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) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;

            heapify(arr, n, largest);
        }
    }

    public static void main(String[] args) {
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
        heapSort(arr);

        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
    }
}

实验结果：

经过测试，以上代码能够正确地对数列进行堆排序，得到正确的排序结果。

实验总结：

通过本次实验，我学习了堆排序算法的原理和实现方法，并通过Java语言编写了相应的代码。堆排序算法具有高效的时间复杂度，在大数据量的情况下具有明显的优势。这次实验让我对Java语言的编程技巧有了更深刻的理解，也对算法的实现有了更深的认识。