【数据结构与算法】【排序】堆排序的代码实现

àì夳堔傛蜴生んèń 2022-08-13 14:48 189阅读 0赞

堆排序是一种选择排序。

前提：数组元素a\[0\]用作哨兵或临时变量，a\[1\]~a\[n\]存放n个待排序的元素。

基本思想是：将待排序的序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根结点。将它移到序列尾部，而后将剩余的n-1个序列重新构造成一个大顶堆。如此反复执行，便能得到一个有序序列了。

代码实现：

<span style="font-family:SimSun;font-size:18px;">// Filename: heap_sort.c
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include "public.h"
    
    // 将a[begin]移动到合适的位置构建为大顶堆，前提：a[beging]的左右子树均已是大顶堆
    void HeapAdjust(int a[], int begin, int end)
    {
        int temp = a[begin];
        int i;
    
        // 依次比较并下移a[begin]
        for (i = begin * 2; i <= end; i *= 2)
        {
            // 在a[begin]及其儿子结点a[i]和a[i+1]中找出最大值，将该最大值调整为根结点
            if (i < end && a[i] < a[i + 1]) i++;
    
            if (temp >= a[i]) break;
    
            a[begin] = a[i];
            begin = i;
        }
    
        a[begin] = temp;
    
        return;
    }
    
    // 堆排序（简单选择排序优化版）
    // n个元素序列的各元素下标：[1, 2, ..., n-1, n], a[0]作为临时变量
    // 将待排序元素进行跳跃分割，对分割后的子序列分别进行简单插入排序；而后将跳跃分割的增量进行缩小，最后增量为1时完成排序。
    // 入参n是待排序元素个数，下表从1开始
    void HeapSort(int a[], int n)
    {
        int i;
    
        // 将n个元素构建成大顶堆
        for (i = n / 2; i > 0; i--)
        {
            HeapAdjust(a, i, n);
        }
    
        // 循环获取最大值，并将剩余的元素构建成大顶堆
        for (i = n; i > 1; i--)
        {
            swap(&a[1], &a[i]);
            HeapAdjust(a, 1, i - 1);
        }
    
        return;
    }
    
    // 直接插入排序主函数
    int HeapSortMain()
    {
        int a1[12] = {0xFF, 3, 4, 5, 8, 9, 7, 6, 1, 0, 2, -1};
    
        printf("堆排序演示(a[0]未使用，不参与排序): \n");
    
        printf("排序前：\n");
        printf("a1: ");
        PrintArray(a1, sizeof(a1) / sizeof(int));
        printf("\n");
    
        // 将从a1[1]到a1[10]共10个元素进行排序
        HeapSort(a1, 10);
    
        printf("排序后：\n");
        printf("a1: ");
        PrintArray(a1, sizeof(a1) / sizeof(int));
        printf("\n");
    
        return 0;
    }
    </span>