C语言数据结构堆排序算法_c语言每次堆排序结果的算法

/*
*堆排序（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;

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60