排序算法之堆排序

雨点打透心脏的1/2处 2022-06-14 02:39 202阅读 0赞

问题描述：

输入一个原始数列，把它进行升序排序，从小到大输出。

例如：给定数列如下：  
5 15 99 45 12 1 90 19 33 41

排序后的结果为：  
1 5 12 15 19 33 41 45 90 99

堆排序的基本思想是，建立一棵完全二叉树，不断调整这棵二叉树，保持这棵二叉树一直是一个大顶堆。

参考代码：

#include <stdio.h>
    
    int arr[100], n;
    
    void AdjustHead(int root, int len)
    {
       //调整ID是1-len范围内的堆，使得其成为大顶堆
        int i = 2 * root, temp = arr[root];
        while (i <= len)
        {
            if (i < len && arr[i] < arr[i + 1])//如果左孩子比右孩子小，那么拿右孩子和根节点比较
                i++;
    
            if (temp > arr[i]) //该堆已经是大顶堆了，不用调整了
                break;
            else
            {
       //把大的那个节点赋值给根节点，并且把根节点下移
                arr[i / 2] = arr[i];
                i *= 2;
            }
        }
        arr[i / 2] = temp;
    }
    
    void  MySwap(int *pNum1, int *pNum2)
    {
        if (NULL == pNum1 || NULL == pNum2)
            return;
    
        int temp = *pNum1;
        *pNum1 = *pNum2;
        *pNum2 = temp;
    }
    
    void PrintArray()
    {
        int i;
        for (i = 1; i <= n; i++)
            printf("%d ", arr[i]);
        printf("\n");
    }
    
    int main()
    {
        int i;
        scanf_s("%d", &n);
        for (i = 1; i <= n; i++)//堆的下标从1开始，操作更方便
            scanf_s("%d", &arr[i]);
    
        printf("排序前\n");
        PrintArray();
        for (i = n / 2; i >= 1; i--)//从ID大的往ID小的节点进行调整，最后保证整个堆是一个大顶堆
            AdjustHead(i, n);
    
        for (i = n - 1; i >= 1; i--)
        {
            MySwap(&arr[1], &arr[i + 1]);//把堆顶的最大的元素扔到最后，这样可以实现从小到大排序
            AdjustHead(1, i);
        }
    
        printf("排序后\n");
        PrintArray();
        return 0;
    }

运行结果：

![这里写图片描述][SouthEast]

[SouthEast]: /images/20220614/e4d803f638284510bc1bd253bef70ae0.png