【大话数据结构C语言】68 堆排序

约定不等于承诺〃 2022-10-15 00:47 209阅读 0赞

堆排序算法是利用堆进行排序的方法

基本思想是将待排序的序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根结点。

将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值，如此反复执行，最后就可以得到一个有序序列了

堆排序的时间复杂度为nlogn，这个性能要远远好于冒泡，简单选择，直接插入排序的时间复杂度

空间复杂度上，它只有一个用来交换的暂存单元，也是非常的不错

但是由于记录的比较与交换是跳跃式进行，因此堆排序也是一种不稳定的排序方法

另外，由于初始构建堆需要比较次数很多，所以不适合待排序个数比较少的情况

![20210522233713935.gif][]

![20210522233713353.gif][]

#include <stdio.h>
    
    int count = 0;
    
    void swap(int k[], int i, int j)
    {
        int temp;
    
        temp = k[i];
        k[i] = k[j];
        k[j] = temp;
    }
    
    void HeapAdjust(int k[], int s, int n)
    {
        int i, temp;
    
        temp = k[s];
    
        for( i=2*s; i <= n; i*=2 )
        {
            count++;
            if( i < n && k[i] < k[i+1] )
            {
                i++;
            }
    
            if( temp >= k[i] )
            {
                break;
            }
    
            k[s] = k[i];
            s = i;
        }
    
        k[s] = temp;
    }
    
    void HeapSort(int k[], int n)
    {
        int i;
    
        for( i=n/2; i > 0; i-- )
        {
            HeapAdjust(k, i, n);
        }
    
        for( i=n; i > 1; i-- )
        {
            swap(k, 1, i);
            HeapAdjust(k, 1, i-1);
        }
    }
    
    int main()
    {
        int i, a[10] = {-1, 5, 2, 6, 0, 3, 9, 1, 7, 4};
    
        HeapSort(a, 9);
    
        printf("总共执行 %d 次比较!", count);
        printf("排序后的结果是：");
        for( i=1; i < 10; i++ )
        {
            printf("%d", a[i]);
        }
        printf("\n\n");
    
        return 0;
    }

[20210522233713935.gif]: /images/20221014/95b20eed00ce4b87b05bf10dd0828f08.png
[20210522233713353.gif]: /images/20221014/9a6bf79d9383411eb5d63f793f447f22.png