84 lines
1.9 KiB
C
84 lines
1.9 KiB
C
// 堆排序，作者：C语言技术网（www.freecplus.net）码农有道。
|
||
#include <stdio.h>
|
||
#include <stdlib.h>
|
||
|
||
// 交换两个元素的值。
|
||
void swap(int *a,int *b) { int temp=*b; *b=*a; *a=temp; }
|
||
|
||
// 采用循环实现heapify（元素下沉）。
|
||
// arr-待排序数组的地址，start-待heapify节点的下标，end-待排序数组最后一个元素的下标。
|
||
void heapify(int *arr,int start,int end)
|
||
{
|
||
// 确定父节点和左子节点的数组下标。
|
||
int dad=start;
|
||
int son=dad*2+1;
|
||
|
||
// 如果子节点的下标没有超出范围，循环继续。
|
||
while (son<=end)
|
||
{
|
||
// 先比较两個子节点大小，选择最大的。
|
||
if ((son+1<=end) && (arr[son]<arr[son+1])) son++;
|
||
|
||
// 如果父节点大于子节点代表调整完毕，直接跳出函数。
|
||
if (arr[dad]>arr[son]) return;
|
||
|
||
// 否则交换父子內容再继续子节点和孙节点比较。
|
||
swap(&arr[dad],&arr[son]);
|
||
dad=son;
|
||
son=dad*2+1;
|
||
}
|
||
}
|
||
|
||
// 采用递归实现heapify。
|
||
void heapify1(int *arr,int start,int end)
|
||
{
|
||
// 确定父节点和左子节点的数组下标。
|
||
int dad=start;
|
||
int son=dad*2+1;
|
||
|
||
// 如果子节点的下标没有超出范围，循环继续。
|
||
if (son>end ) return;
|
||
|
||
// 先比较两個子节点大小，选择最大的。
|
||
if ((son+1<=end) && (arr[son]<arr[son+1])) son++;
|
||
|
||
// 如果父节点大于子节点代表调整完毕，直接跳出函数。
|
||
if (arr[dad]>arr[son]) return;
|
||
|
||
// 否则交换父子內容再继续子节点和孙节点比较。
|
||
swap(&arr[dad],&arr[son]);
|
||
|
||
heapify(arr,son,end);
|
||
}
|
||
|
||
void heapsort(int *arr, int len)
|
||
{
|
||
int ii;
|
||
|
||
// 初始化堆，从最后一個父节点开始调整。
|
||
for (ii=(len-1)/2;ii>=0;ii--) heapify(arr,ii,len-1);
|
||
|
||
// 把第一个元素和堆最后一个元素交换，然后重新调整，直到排序完毕。
|
||
for (ii=len-1;ii>0;ii--)
|
||
{
|
||
swap(&arr[0],&arr[ii]);
|
||
heapify(arr,0,ii-1);
|
||
}
|
||
}
|
||
|
||
int main()
|
||
{
|
||
int arr[]={44,3,38,5,47,15,36,26,27,2,46,4,19,50,48};
|
||
|
||
int len=sizeof(arr)/sizeof(int);
|
||
|
||
heapsort(arr,len);
|
||
|
||
// 显示排序结果。
|
||
int yy; for (yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");
|
||
|
||
// system("pause"); // widnows下的C启用本行代码。
|
||
|
||
return 0;
|
||
}
|