堆排序--C语言

我就是我 2022-03-19 01:54 185阅读 0赞

昨天写了选择排序中的简单选择排序，今天把另一种选择排序算法–堆排序写一下。以前一直对堆排序有所误解，现在再次去学习才知当日只是明白了调整堆的算法，而不知道实际具体的排序，现在想来还是当时对自己太仁慈的缘故。  
  将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重新又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫堆排序。  
  由此，实现堆排序需要解决两个问题：  
  (1)如何由一个无序序列建成一个堆?  
  (2)如何在输出堆顶元素之后，调整剩余元素成为一个新的堆?  
代码如下：

#include<stdio.h>
    
    /*
     * 堆排序--调整堆，arr为待调整数组，s为开始位置，e为最大长度*/
    void AdjHeap(int arr[],int s,int e)
    {
        
        int j = 0;
        for(j = 2 * s;j <= e;j = j * 2)
        {
        
            if(arr[j] < arr[j + 1])
            {
        
                j++;
            }
            if(arr[s] < arr[j])
            {
        
                arr[0] = arr[s];
                arr[s] = arr[j];
                arr[j] = arr[0];
            }
            s = j;
        }
    }
    
    /*
     * 堆排序*/
    void HeapSort(int arr[],int len)
    {
        
        int i = 0;
        int j = 0;
        for(i = len/2;i > 0;i--)
        {
        
            AdjHeap(arr,i,len);
        }
        for(i = len - 1;i > 0;i--)
        {
        
            arr[0] = arr[i + 1];
            arr[i + 1] = arr[1];
            arr[1] = arr[0];
            AdjHeap(arr,1,i);
        }
    }
    
    int main()
    {
        
        int arr[] = {
        0,39,28,40,6,9,12,8};
        int i = 0;
        for(i = 1;i < 8;i++)
        {
        
            printf("%d ",arr[i]);
        }
        printf("\n");
        HeapSort(arr,7);
        for(i = 1;i < 8;i++)
        {
        
            printf("%d ",arr[i]);
        }
        printf("\n");
        return 0;
    }

堆排序适用于len比较大的情况，其时间复杂度为O(nlogn)，堆排序也是一种不稳定的排序算法。