C语言数据结构堆排序算法

Bertha 。 2022-01-21 23:57 303阅读 0赞

/\*  
\*堆排序（heapsort） 是选择排序的升级版 降低了排序函数的冗余性  
\*堆排序分为 大顶堆 和小顶堆 大顶堆为堆顶为最大元素 小顶堆为堆顶为最小元素  
\*先建立堆 再调整 最后输出 堆的元素  
\*建立在二叉树的基础上  
\*/

void HeapSort(int *s,int length);//堆排序函数
    void HeapAdjust(int *s,int i,int length);//堆排序的辅助函数
    void main()
    {
        int m;
        int n[100];//待排序的数组
        int i;
        printf("请输入要输入的数据个数:\n");
         scanf("%d",&m);
         printf("请依次输入数据:\n");
         for(i=0;i<m;i++)
           scanf("%d",&n[i]);
           printf("堆排序遍历结果为:\n");
           HeapSort(n,m);
           for(i=0;i<m;i++)
            printf("%d\t",n[i]);
    
    }
    void HeapSort(int *s,int length)
    {
        int i;
        int temp;//交换中间变量
        //创建大顶堆
        for(i=length/2-1;i>=0;--i)//length/2-1为最后 一个非叶子节点
            HeapAdjust(s,i,length);
        //将堆中的元素按递增的排序输出
        //将最后一个元素和第一个元素替换 始终保持每次循环调整之后最后一个元素是最大元素
        //循环条件是为了让每次调整之后的第一个元素为最大元素  以便之后的数值交换
        //直到循环到第一个元素结束  到main函数中进行输出
        for(i=length-1;i>0;--i)//将最后一个元素和第一个元素进行交换
        {
            temp=s[i];//第一个元素的值和最后一个元素的值进行交换
            s[i]=s[0];
            s[0]=temp;
            HeapAdjust(s,0,i);//用于调整第一个元素的值  使其保持为调整后的最大值 
                                                                              // 为下一次循环创造条件
        }
    }
    void HeapAdjust(int *s,int i,int length)
    {
        int child;//孩子节点在数组中下标
        int temp;//中间变量
        for( ;2*i+1<length;i=child)
        {
            child=2*i+1;//得到根节点的左孩子节点在数组中的下标
            if(child<length-1&&s[child]<s[child+1])//左节点小于其右节点的值
            //并判断是否存在其右节点
              child++;//将孩子节点的下标指向其右孩子节点
              if(s[i]<s[child])
              {
                  temp=s[i];//进行数值交换
                  s[i]=s[child];
                  s[child]=temp;
              }
              else
                break;
    
        }
    }