C语言 数据结构堆排序顺序存储（升序）

C语言 数据结构堆排序顺序存储（升序）攻略

1. 堆排序概述

堆排序是一种常见的排序算法，通过构建最大堆或最小堆来实现排序。本文介绍的是使用顺序存储方式实现的最大堆排序，也就是升序排序。

2. 最大堆的定义和实现

最大堆指的是堆结构中父节点的值大于子节点的值，根节点的值最大。对于一棵完全二叉树，若父节点的下标为i，则其左子节点的下标为2i+1，右子节点的下标为2i+2。下面是最大堆的实现代码：

void adjustHeap(int a[], int i, int n)
{
    int j, temp = a[i];
    for (j = 2 * i + 1; j < n; j = 2 * j + 1)
    {
        if (j < n - 1 && a[j] < a[j+1])
            ++j;

        if (temp >= a[j])
            break;

        a[i] = a[j];
        i = j;
    }
    a[i] = temp;
}

void buildHeap(int a[], int n)
{
    int i;
    for (i = n / 2 - 1; i >= 0; --i)
        adjustHeap(a, i, n);
}

其中，adjustHeap是调整堆的函数，用于将以i为父节点的子树调整为最大堆，n为数组大小；buildHeap是建堆函数，用于将整个数组调整为最大堆。

3. 堆排序的实现

堆排序的过程就是不断将堆顶元素（最大值）与堆底元素交换，再调整剩余元素为最大堆，以此类推，直到整个数组有序。堆排序的实现代码如下：

void heapSort(int a[], int n)
{
    int i, temp;
    buildHeap(a, n);
    for (i = n - 1; i > 0; --i)
    {
        temp = a[0];
        a[0] = a[i];
        a[i] = temp;
        adjustHeap(a, 0, i);
    }
}

其中，buildHeap调整整个数组为最大堆，heapSort函数则用于完成整个堆排序的过程。

4. 示例说明

示例一

假设一个数组为{7, 3, 1, 5, 2, 4, 6}，经过堆排序过程后，数组应该为{1, 2, 3, 4, 5, 6, 7}，下面是详细的堆排序过程：

1. 首先调整整个数组为最大堆，得到{7, 5, 4, 3, 2, 1, 6}
2. 将堆顶元素7与堆底元素6交换，得到{6, 5, 4, 3, 2, 1, 7}，此时下标为0~5的元素为最大堆
3. 将堆顶元素6与堆底元素1交换，得到{1, 5, 4, 3, 2, 6, 7}，此时下标为0~4的元素为最大堆
4. 将堆顶元素1与堆底元素2交换，得到{2, 5, 4, 3, 1, 6, 7}，此时下标为0~3的元素为最大堆
5. 将堆顶元素2与堆底元素3交换，得到{3, 5, 4, 2, 1, 6, 7}，此时下标为0~2的元素为最大堆
6. 将堆顶元素3与堆底元素1交换，得到{1, 5, 4, 2, 3, 6, 7}，此时下标为0~1的元素为最大堆
7. 将堆顶元素1与堆底元素0交换，得到{1, 5, 4, 2, 3, 6, 7}，此时整个数组有序

示例二

假设一个数组为{1, 2, 3, 4, 5, 6, 7}，经过堆排序过程后，数组应该还是{1, 2, 3, 4, 5, 6, 7}，因为数组已经有序，所以只需调用buildHeap函数构建最大堆即可。

5. 总结

堆排序是一种常见的排序算法，其时间复杂度为O(nlogn)。本文介绍了使用顺序存储方式实现的最大堆排序，包括最大堆的定义和实现，以及堆排序的具体实现过程和示例说明。