JAVA算法起步之堆排序实例

// Java堆排序示例
import java.util.Arrays;

public class HeapSort {
    // 堆化函数，从给定的节点开始向下堆化
    private 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 swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // 递归地堆化受影响的子树
            heapify(arr, n, largest);
        }
    }

    // 堆排序函数
    public 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--) {
            // 移动当前根到末尾
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 调用max heapify在减少的堆上
            heapify(arr, i, 0);
        }
    }

    // 测试堆排序
    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};
        int n = arr.length;

        HeapSort ob = new HeapSort();
        ob.sort(arr);

        System.out.println("Sorted array is");
        System.out.println(Arrays.toString(arr));
    }
}

这是一个Java实现的堆排序示例。堆排序是一种利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。堆排序可以分为两个主要的过程：建立堆和调整堆。在建立堆的过程中，我们将原始数组重新排列成一个最大堆。然后，我们通过反复移除堆顶元素（即当前最大元素），并替换以堆的最后一个元素，然后重新调整堆以维持其最大堆的特性，来完成排序。