十大经典排序算法(动图演示)-3之堆排序

1.1 算法描述

涉及到原地建堆的基本公式及概念：

1. 父节点i的左子节点的位置：2i+1
2. 父节点i的右子节点的位置：2i+2
3. 子节点i的父节点的位置： (i-1)/2
4. 完全二叉树中第一个非叶子节点的位置：元素个数/2

算法描述

1. 原地建堆
2. 交换堆顶元素与尾部元素
3. 对的元素数量减少1
4. 对0的位置进行一次siftDown(恢复堆的特性)
5. 重复 2、3、4步骤

1.2 动图演示

1.3 代码实现

以下是一个用Java实现的堆排序算法：

public class HeapSort {  
    // 主方法，用于测试堆排序  
    public static void main(String[] args) {  
        int[] array = {12, 11, 13, 5, 6, 7};  
        int n = array.length;  
  
        System.out.println("原始数组:");  
        printArray(array);  
  
        heapSort(array, n);  
  
        System.out.println("排序后的数组:");  
        printArray(array);  
    }  
  
    // 堆排序方法  
    public static void heapSort(int[] array, int n) {  
        // 构建最大堆  
        for (int i = n / 2 - 1; i >= 0; i--) {  
            heapify(array, n, i);  
        }  
  
        // 一个一个从堆顶取出元素  
        for (int i = n - 1; i > 0; i--) {  
            // 移动当前根到数组末尾  
            int temp = array[0];  
            array[0] = array[i];  
            array[i] = temp;  
  
            // 调整剩余堆  
            heapify(array, i, 0);  
        }  
    }  
  
    // 堆调整方法  
    public static void heapify(int[] array, int n, int i) {  
        int largest = i;    // 初始化最大值为根节点  
        int left = 2 * i + 1;  // 左子节点  
        int right = 2 * i + 2; // 右子节点  
  
        // 如果左子节点大于根节点  
        if (left < n && array[left] > array[largest]) {  
            largest = left;  
        }  
  
        // 如果右子节点大于当前最大值  
        if (right < n && array[right] > array[largest]) {  
            largest = right;  
        }  
  
        // 如果最大值不是根节点  
        if (largest != i) {  
            int swap = array[i];  
            array[i] = array[largest];  
            array[largest] = swap;  
  
            // 递归调整受影响的子树  
            heapify(array, n, largest);  
        }  
    }  
  
    // 打印数组方法  
    public static void printArray(int[] array) {  
        int n = array.length;  
        for (int i = 0; i < n; ++i) {  
            System.out.print(array[i] + " ");  
        }  
        System.out.println();  
    }  
}

代码解释：

1. main方法：测试堆排序算法，首先打印原始数组，然后调用heapSort方法进行排序，最后打印排序后的数组。

2. heapSort方法：首先通过heapify方法构建最大堆，然后从堆顶（数组的第一个元素）开始，一个一个取出元素放到数组的末尾，并调整剩余部分继续形成最大堆，直到所有元素都排序完成。

3. heapify方法：这是一个递归方法，用于调整堆结构，确保堆的性质被维护。它比较根节点与其左右子节点，如果子节点大于根节点，则进行交换，并递归地调整受影响的子树。

4. printArray方法：用于打印数组元素。

堆排序的步骤：

1. 构建最大堆：从最后一个非叶子节点开始，逐层向上调整堆结构，直到根节点。

2. 排序：将堆顶元素（最大值）与当前未排序部分的最后一个元素交换，然后调整剩余部分继续形成最大堆，重复这个过程直到所有元素排序完成。

通过这种方法，堆排序可以在O(n log n)的时间复杂度内完成排序。