【转】c语言版堆排序 - 数学建模社区-数学中国

#include<stdio.h>
( A2 s+ }/ @: [) Z& [+ I4 t. F
#include<stdlib.h># V# H( H0 b9 G( @
#include<time.h>7 \6 p5 A4 h: P* E `5 U+ i" e# h% r4 {
#define random(i) (rand()%i): r3 l9 Z0 z) g$ T Y' f
#define N 15% r( h* Z7 u Z/ j3 A3 ]1 K( q
) ]# R8 s4 b) k( {/ K
//维护堆的性质，这里是用的最大堆
8 M3 ~- a9 U$ n0 U' r6 G
//且为二叉堆
, V Y" F' N8 J" b& S5 ~/ F
void MAX_HEAPIFY(int A[],int i,int heapSize){9 ]( B1 A- }8 m% h
int l;//表示节点i的左孩子
1 W+ R6 a3 R- s3 A! V
int r;//表示节点i的右孩子! u, M+ D' J( t$ b
int largest;//表示最大元素，也就是根.( R/ G* @* q! x" E! X# l7 s/ g
int temp;//临时变量，用于交换2 L, l3 {' }5 y
int k;
0 z7 k5 _5 j" T1 O2 E, ]( q
l=2*i+1;
2 i" J& g: m8 e _ h* ~
r=2*i+2;
! m2 g* w* N: o& G x2 _7 D" G
if((l<heapSize)&&(A[l]>A[i])) //如果左孩子大，那么记下下标7 s# y+ X2 d- A5 X6 h
{
3 M. O# z3 H) g/ o% a: x. v8 y
largest=l;
2 z, G% R; o3 D8 Z/ v/ ?8 [
}
* Q2 e9 s" i1 Q" r+ g
else' F$ S3 \8 F' y9 _* K
{% k; t; e( `8 R3 g3 l. }0 J
largest=i;
7 d" N# D; ^0 z: m) f0 _) l! S
2 d \# P) \; l
}
) C$ O: O3 n/ n! h- w
if ((r<heapSize)&&(A[r]>A[largest]))
- Z4 s# q5 X5 i+ s
{1 S. n& S" e0 \& W3 P+ B# k
largest=r;, k# g7 ~8 ]2 d6 z: `
}
- w {! j \4 B* p% R! I
if (largest!=i)& l4 G0 B0 g5 n3 n y) v0 h
{
- v- ^ H+ _$ d/ A2 Z3 |
temp=A[i];: u! ?; m0 \! i& t4 M
A[i]=A[largest];0 n g3 }; S1 @" u9 D
A[largest]=temp;
: h4 I2 a. t- f O
//递归调用# O* _1 j* C$ T1 h3 `: t
MAX_HEAPIFY(A,largest,heapSize);
|, U* P" h; J5 ^* x7 O
}
# D, f ]' s( A) x9 a6 Y
; O6 n ]! @( L, W$ K! K
}
. }9 O) J' T3 Q- r# `- C. W6 d
. ~( c& Q& h) }) M) [ @
//建堆, M7 a. ?2 A( N# {+ G5 L8 G
void BUILD_HEAP(int A[]){
8 C7 u' H$ U- @9 _" m) L5 V
int i;
- j$ m+ _- c1 r4 Q' L
for (i=N/2-1;i>=0;i--)
9 j$ f2 e/ w) S8 G
{: Q' h, o% m6 `1 C% K T( E
MAX_HEAPIFY(A,i,N);2 a; e: B) Y3 G- v; j6 \
}2 F4 d9 A8 f1 }+ ]" r3 k
# |1 [$ Q) a6 I/ P% d( W$ s5 i, V7 `
}6 H0 O7 `8 M& F) p& Z5 B$ W
$ g4 Y# u9 ]9 i
//堆排序
" k W' `4 _2 y6 d4 _- E
void HEAP_SORT(int A[]){1 F3 a/ b8 ]. y5 M9 ^8 z @6 M
int i;5 B( l* `) U( Q
int j=0;# m9 }" }9 B2 q: t1 C- ~
int temp; //交换时用的临时变量, u; e9 O+ R' O# t( O) S
int size=N; //size代表元素个数. I+ D5 V( `8 i* W- s
//先建堆2 g2 \3 }9 \6 E" O6 l" l/ p$ L9 `" u
BUILD_HEAP(A);5 B! V" f" u7 Q7 U8 t2 K. J
for(i=N-1;i>0;i--)4 P7 ~, w9 w% O0 t; V& b. W
{
8 q( D. h/ n& X# ~) o
//因为根节点总是最大的数，我们每次把根节点换到相应位置即可实现排序
. y- ^0 O9 `* C0 f
//堆排序的时间复杂度为O（nlgn）) d) }9 ~' Q% T" J4 W3 W6 t
temp=A[i];
8 ]: M+ g2 B, i \1 H& @) D. E
A[i]=A[0];
# B6 s7 a# J- r/ F0 e( C
A[0]=temp;
4 I8 w8 b, g7 y% ~& ^! R; C
size--;
, n$ C5 X4 [! _1 A1 N; L2 R0 B
MAX_HEAPIFY(A,0,size);$ o |# z$ g) V
! U% L) ?( U, X
}! P0 |1 w: Q3 p2 k
for(j=0;j<N;j++). a# ?% [% f0 a2 \- D
{
$ Q6 j2 i9 R4 B& \2 D# V
printf("%5d",A[j]);
- e& }6 d3 i6 k* c
}+ v: o0 k' G) A
5 S# o9 h P! k
}
' v6 n' F0 |" E$ C$ d
void main(){! r* ~: m! ]" U2 J4 n U
# N/ i4 p* ^! ~- I: c
int rand_no=0;. y3 F1 ^4 n- O; Z0 A& T8 ]5 J
int i=0;* ?+ e+ f4 W H9 T5 G: O
int a[N]; //n表示数组长度4 \' T% s) d9 p! H# U- S: E$ p, H4 u1 |
srand((int)time(0)); //设置随机数种子% ? q7 _7 a4 [' I. V
printf("==============================排序前=========================================");! z! \) f- K! G7 t# Y: z
printf("\n");
. C, r8 o1 J+ ^* o
for(rand_no=0;rand_no<N;rand_no++)1 O# M' g, B( N7 ^! H7 ~( e, M
{+ t( a( ]$ s( q/ R! ~. l% L7 _8 b
8 e3 R& ~4 L' P K
a[rand_no]=random(100);
" ~ t8 X# o, j% k) q
printf("%5d",a[rand_no]);; t {; ~+ N- A5 _
) r$ F6 I1 U0 m1 d
}
. K9 c1 u6 E% I
printf("\n");5 J3 e* `# ]% ^! z
printf("==============================排序后=========================================\n");4 w) v/ z, A7 p! E/ v4 l9 a1 J
HEAP_SORT(a);
' k7 _5 W: w" A8 O' k V1 U
printf("\n");
$ ]$ F; U3 M0 f: R4 l7 l, r
' A, t' q: s0 X( r' J% l) _
' P- l9 j) p/ P$ G. M0 _' `
}. v( z! t5 `2 l

复制代码