堆排序法（Java & C/C++ 实现）

一、前言

堆排序是利用堆这种数据结构而设计的一种排序算法。时间复杂度为 O(n * lg n)。

介绍堆排序前，我们先介绍一下堆的相关概念，如果你对堆的概念还不熟悉的话可以看看。

 

二、堆

1. 示意图

2. 性质

除最底层外，该树是完全充满的，且是从左到右填充。

树的根结点是 A[ 1 ]，若某一结点下标为 i，则很容易得到它的父节点为 i/2，左子结点为 2i，右子结点为 2i + 1。

注意： 数组的索引是 0 开始的，其左右子结点分别为 2i + 1 和 2i + 2。

3. 最大堆和最小堆

最大堆即父结点的值大于等于子结点的值；最小堆即父结点的值小于等于子结点的值。

4. 应用

堆是一个很有用的数据结构，它的一个常见应用即：优先队列 。

 

三、代码实现

主要是 3 个方法：

heapSort() 方法进行堆排序，里面会调用 buildHeap() 方法和 maxHeapify() 方法。

buildHeap() 方法将一个数组构建为一个最大堆。

maxHeapify() 方法调整堆，使得这个堆满足最大堆的性质。

1. Java

public class Main {

    public static void main(String[] args) {
        int[] arr = new int[] { 16, 4, 10, 14, 7, 9, 3, 2, 8, 1 };
        heapSort(arr);
        printArray(arr);
    }

    public static void heapSort(int[] arr) {
        buildHeap(arr); // 首先建立堆
        int heapSize = arr.length;
        for (int i = arr.length - 1; i > 0; i--) {
            // 取出最大值放在数组末端。由于堆的特性最大值总是在 a[0] 处
            int max = arr[0];
            arr[0] = arr[i];
            arr[i] = max;
            // 重新调整堆
            maxHeapify(arr, 0, --heapSize);
        }
    }

    public static void buildHeap(int[] arr) {
        // 堆的最后一个分支结点索引为 arr.length / 2 - 1
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            maxHeapify(arr, i, arr.length);
        }
    }

    public static void maxHeapify(int[] arr, int index, int heapSize) {
        int leftIndex = index * 2 + 1; // 左子节点对应数组中的索引
        int rightIndex = index * 2 + 2; // 右子节点对应数组中的索引
        int maxIndex = index;
        // 如果左子结点较大，则将最大值索引设为左子节点
        if (leftIndex < heapSize && arr[leftIndex] > arr[index]) {
            maxIndex = leftIndex;
        }
        // 如果右子结点比 max(this, left)还大，则将最大值索引设为右子节点
        if (rightIndex < heapSize && arr[rightIndex] > arr[maxIndex]) {
            maxIndex = rightIndex;
        }
        // 如果当前结点的值不是最大的，则需要交换最大值，并继续遍历交换后的子结点
        if (maxIndex != index) {
            int temp = arr[maxIndex];
            arr[maxIndex] = arr[index];
            arr[index] = temp;
            maxHeapify(arr, maxIndex, heapSize); // 结点的计数比索引值大1
        }
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}

2. C/C++

代码实现基本没什么差异。

#include <stdio.h>

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void maxHeapify(int *arr, int index, int heapSize)
{
    int leftIndex = index * 2 + 1; // 左子节点对应数组中的索引
    int rightIndex = index * 2 + 2; // 右子节点对应数组中的索引
    int maxIndex = index;
    // 如果左子结点较大，则将最大值索引设为左子节点
    if (leftIndex < heapSize && arr[leftIndex] > arr[index])
    {
        maxIndex = leftIndex;
    }
    // 如果右子结点比 max(this, left)还大，则将最大值索引设为右子节点
    if (rightIndex < heapSize && arr[rightIndex] > arr[maxIndex])
    {
        maxIndex = rightIndex;
    }
    // 如果当前结点的值不是最大的，则需要交换最大值，并继续遍历交换后的子结点
    if (maxIndex != index)
    {
        swap(&arr[index], &arr[maxIndex]);
        maxHeapify(arr, maxIndex, heapSize); // 结点的计数比索引值大1
    }
}

void buildHeap(int *arr, int length)
{
    // 堆的最后一个分支结点索引为 arr.length / 2 - 1
    for (int i = length / 2 - 1; i >= 0; i--)
    {
        maxHeapify(arr, i, length);
    }
}

void heapSort(int *arr, int length)
{
    buildHeap(arr, length); // 首先建立堆
    int heapSize = length;
    for (int i = length - 1; i > 0; i--)
    {
        // 取出最大值放在数组末端。由于堆的特性最大值总是在 a[0] 处
        swap(&arr[0], &arr[i]);
        // 重新调整堆
        maxHeapify(arr, 0, --heapSize);
    }
}

void printArray(int *array, int length)
{
    for (int i = 0; i < length; i++)
    {
        printf("%d ", array[i]);
    }
}

int main()
{
    int arr[] = { 16, 4, 10, 14, 7, 9, 3, 2, 8, 1 };
    heapSort(arr, sizeof(arr) / sizeof(arr[0]));
    printArray(arr, sizeof(arr) / sizeof(arr[0]));
    return 0;
}

执行结果

1 2 3 4 7 8 9 10 14 16 

​