c语言堆排序代码

c语言堆排序代码

#include

void shift(int a[] , int i , int m)
{
int k , t;

t = a[i]; k = 2 * i + 1;
while (k < m)
{
if ((k < m - 1) && (a[k] < a[k+1])) k ++;
if (t < a[k]) {a[i] = a[k]; i = k; k = 2 * i + 1;}
else break;
}
a[i] = t;
}

void heap(int a[] , int n) //a 为排序数组，n为数组大小（编号0-n-1）
{
int i , k;

for (i = n/2-1; i >= 0; i --) shift(a , i , n);
for (i = n-1; i >= 1; i --)
{
k = a[0]; a[0] = a[i]; a[i] = k;
shift(a , 0 , i);
}

}
void main()
{
int a[10],i;
for(i=0;i<10;i++)
scanf("%d",&a[i]);
heap(a,10);
for(i=0;i<10;i++)
printf("%d",a[i]);
}

不明白LZ为什么拒绝指针，不过我写的本来就“没有”指针——数组名就是指针的说。以下，“摆渡”二字请用'\t'（跳格符）替换。
#include
#define NP1 11
double a[NP1]={0,9,5,3,6,7,1,4,8,2,6};//NP1 means N Plus 1, that is, a[0] is for temp.
static unsigned short top=NP1-1,n;
void correct()
{
while(2*n<=top)
摆渡{
if(2*n摆渡摆渡{
//When Left==Right>Centre, Left instead of Right should tend to swap.
//Otherwise, when it is like Centre==Left, they will swap several times.
if(a[2*n]摆渡摆渡摆渡{
if(a[n]摆渡摆渡摆渡摆渡{
a[0]=a[n];a[n]=a[2*n+1];a[2*n+1]=a[0];
n=2*n+1;
摆渡摆渡摆渡摆渡}
else return;
摆渡摆渡摆渡}
else goto m2p1nu;
摆渡摆渡}
else
摆渡摆渡{
m2p1nu:
if(a[n]摆渡摆渡摆渡{
a[0]=a[n];a[n]=a[2*n];a[2*n]=a[0];
n*=2;
摆渡摆渡摆渡}
else return;
摆渡摆渡}
摆渡}
}
int main()
{
//Form the tree using FOR.
for(unsigned short m=(NP1+1)/2;--m;)
摆渡{
n=m;
correct();
摆渡}
//Hmm, pick the fruit. The direction will turn about, unavoidably.
while(top>2)
摆渡{
a[0]=a[1];a[1]=a[top];a[top--]=a[0];
n=1;
correct();
摆渡}
a[0]=a[1];a[1]=a[2];a[2]=a[0];
for(n=NP1;--n;) printf("%g\t",a[n]);
getchar();
return 0;
}

#include
#define SIZE 10
#define Left(i) ((i) << 1)
#define Right(i) (((i) << 1) + 1)
void heapsort(int a[], int heapsize);
void maxheapify(int a[], int i, int heapsize);
void swap(int *x, int *y);
int main(int argc, char **argv)
{
int a[SIZE+1] = { 0, 16, 4, 10, 14, 7, 9, 3, 2, 8, 1 };

int i, heapsize;
heapsize = SIZE;
heapsort(a, heapsize);
for (i = 1; i < SIZE + 1; i++)
printf("%d ", a[i]);
printf("\n");
return 0;
}

void heapsort(int a[], int heapsize)
{
int i;
for (i = heapsize / 2; i >= 1; i--)
maxheapify(a, i, heapsize);
for (i = heapsize; i >= 2; i--)
{
swap(&a[1], &a[i]);
heapsize--;
maxheapify(a, 1, heapsize);
}
}

void maxheapify(int a[], int i, int heapsize)
{
int largest, left, right;
left = Left(i);
right = Right(i);
if (left <= heapsize && a[left] > a[i])
largest = left;
else
largest = i;
if (right <= heapsize && a[right] > a[largest])
largest = right;
if (largest != i)
{
swap(&a[i], &a[largest]);
maxheapify(a, largest, heapsize);
}
return;
}
void swap(int *x, int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
不用指针。。。？C的精髓就在此，还是好好理解好吧