排序算法之堆排序
基本思想：
在堆排序的算法中先建一个大顶堆，既先选得一个关键字作为最大的记录并与序列中最后一个记录交换，然后对序列中前N-1记录进行选择，重新将它调整成一个大顶堆，如此反复直到排序结束。
#include <stdio.h>
const int Length = 10; //堆大小
void Max_Heapify(int [], int, int);
void Build_Max_Heap(int []);
void HeapSort(int [], int);
/*单一子节点最大堆调整*/
void Max_Heapify(int L[], int i, int length)
{
int l = 2*i+1;/*根节点为0时，i的左子节点*/
int r = 2*i+2;/*右子节点*/
int largest;
int temp;
if(l < length && L[l] > L[i])
{
largest = l;
}
else
{
largest = i;
}
if(r < length && L[r] > L[largest])
{
largest = r;
}
if(largest != i)
{
temp = L[i];
L[i] = L[largest];
L[largest] = temp;
Max_Heapify(L, largest, length);//交换后的子节点比父节点小，
//但不能保证交换过来的子节点比他的子节点小，所以要递归，使子节点为根的子树也是最大堆
}
}
/*建立初始最大堆*/
void Build_Max_Heap(int L[])
{
int i,j;
for(i = Length/2; i >= 0; i--)
{
Max_Heapify(L, i, Length);
}
}
/*堆排序*/
void HeapSort(int L[], int length)
{
int temp;
int i;
Build_Max_Heap(L);
for(i = length - 1; i >= 1; i--)
{
temp = L[0];// 交换堆顶和堆尾，取得最大值
L[0] = L[i];
L[i] = temp;
length = length - 1;//整个数组元素个数减1
Max_Heapify(L, 0, length);//对新数组生成最大堆
}
for(i = 0; i < Length;i++)
{
printf("%d ", L[i]);
}
printf("\n");
}
int main()
{
int L[10]={4,9,2,6,0,8,3,7,5,1},i;
HeapSort(L, Length);
system("pause");
return 0;
}
creat by 张飞雪
补充：软件开发 , 其他 ,
