#include<stdio.h>
void Show(int arr[], int n)
{
int i;
for ( i=0; i<n; i++ )
printf("%d ", arr[i]);
printf("\n");
}
// 交换数组元素位置
void Swap( int *num_a, int *num_b )
{
int temp = *num_b;
*num_b = *num_a;
*num_a = temp;
}
// 创建大根堆算法
void HeapAdjust(int a[], int start, int end)
{
int i,temp;
temp = a[start];
for (i = 2*start+1;i<end;i=i*2+1)
{
if (i+1<end&&a[i]<a[i+1])//右孩子大于左孩子,下标在右孩子上,否则下标在左孩子上
i++;//i代表左右孩子中较大值得下标
if(temp>a[i])//根比左右都大,跳出循环
break;
else{
a[start] = a[i];//把孩子子树中最大的值放在父节点
start = i;
}
}
a[start] = temp;
}
int* HeapBuild(int array[], int length)
{
int i;
for ( i = length / 2 - 1; i >= 0; i--)
{
HeapAdjust(array, i, length);
}
return array;
}
// 堆排序算法
int* HeapSort(int a[],int length){
int i;
a = HeapBuild(a,length);
for(i = length-1;i>0;i--){
Swap(&a[0],&a[i]);
HeapAdjust(a,0,i);
}
return a;
}
int main()
{ //测试数据
int *a;
int arr_test[10] = { 8, 4, 2, 3, 5, 1, 6, 9, 0, 7 };
Show(arr_test,10);
a = HeapSort(arr_test,10);
Show(a,10);
return 0;
}
优化:
#include <stdio.h>
#include <stdlib.h>
int * DuiPaixu(int a[],int n){
int end = n,i,t,x,y;
while(end >= 1){
while(1){
int flag = 0;
i=end/2;
while(i > 0){
if(a[i] < a[2*i]){
t = a[i];
a[i] = a[2*i];
a[2*i] = t;
flag = 1;
}
if(2*i+1 <= end&&a[i] < a[2*i+1]){
x = a[i];
a[i] = a[2*i+1];
a[2*i+1] = x;
flag = 1;
}
i--;
}
if(!flag)
break;
}
y = a[1];
a[1] = a[end];
a[end] = y;
end--;
}
return a;
}
void Print(int a[],int n){
int i;
for(i=1;i<=n;i++){
printf("%5d",a[i]);
}
}
int main(void){
int n,i;
int * a;
printf("请输入数组长度n= ");
scanf("%d",&n);
a=(int*)malloc(n*sizeof(int));
printf("请输入数组元素: ");
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
}
a = DuiPaixu(a,n);
Print(a,n);
return 0;
}
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。