2019-06-25

小根堆对数组排序C语言算法实现

下面是我用C语言实现的小根堆排序算法实现，有注释。空间复杂度仅为o(1). 数组中0也存元素。

个人认为利用堆排序可以查找出数组中重复的2个元素，因为排好序后，数组中重复的2个元素一定是相邻的2个元素，即最多只需要比较n-1次即可找出。

#include <stdio.h>

int heapDown(int[],int,int);

/构造初始堆/
int buildHeap(int a[],int n)
{
int start = (n-1)/2; /需要调整的起始元素/
int j = 0;
for(j=start;j>=0;j–) /从第一个有子节点的节点逐级向上调整/
{
heapDown(a,n,j);
}
}
/**
目前元素的子堆是小根堆,需要从目前元素开始向下调整
_/ int heapDown(int a[],int n,int j) { int k = j; int left,right,min,tmp; while(1) { left = 2_k+1; /左子/
right = 2_k + 2; /右子/ min = k; /当前元素初始为最小/ tmp = 0; if(left>n&&right>n) break; /左右儿子都不存在,调整完成/ if(right>n) /右子不存在,和左子树比较/ { if(a[k]>a[left]) /左子为最小节点/ { min = left; } } else /左右都在/ { tmp = a[left]>a[right]? right:left; /最小为两子的最小/ if(a[k]>a[tmp]) min=tmp; } if(min!=k) /需要调整/ { tmp = a[k]; a[k]=a[min]; a[min]=tmp; k=min; continue; /从调整后的新元素开始继续向下调整/ } break; /不需要调整,调整完成/ }/_while(1)*/
}

int main()
{
int a[]={1,2,4,3,7,8,6};
int n = 7;
int i = 0;
int tmp = 0;
buildHeap(a,6); /构造初始堆/

for(i = 0;i<7;i++) /排序前数组打印/
printf(“i=[%d],”,a[i]);

for(i=0;i<(n-1);i++)
{
tmp=a[0]; /将堆顶与目前的无序数组中的最后一个交换/
a[0]=a[n-i-1];
a[n-i-1]=tmp;
heapDown(a,n-(i+2),0); /因为目前数组除堆顶外是小根堆，故可用heapDown将无序数组调整为小根堆/
}

printf(“n”); /排序后数组打印/
for(i = 0;i<7;i++)
printf(“i=[%d],”,a[i]);

return 0;

}

作者：self-motivation
来源：CSDN
原文：https://blog.csdn.net/happyAnger6/article/details/7273031
版权声明：本文为博主原创文章，转载请附上博文链接！