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

#include<stdio.h>
0 `! x3 H9 B6 t( }' I, z7 N: Q
#include<stdlib.h>
5 O! f" f4 b% G, l; a$ M
#include<time.h>! n# D% ~: P9 j2 y
#define random(i) (rand()%i)( V5 V' `' x' w8 a1 R! a
#define N 159 ]" M& M$ h' l9 [$ Z/ R$ j; E) a
. D) o* F: z, p- b* ^5 x/ X
//维护堆的性质，这里是用的最大堆: d0 @& O! N: ^ [( t
//且为二叉堆
' t3 ?; W! U% [( J- b" v) W @
void MAX_HEAPIFY(int A[],int i,int heapSize){
/ `; t7 e, s. c4 X, o5 V
int l;//表示节点i的左孩子* h$ l5 }( e, D1 {
int r;//表示节点i的右孩子( c. a5 q- \2 B" }/ E7 C
int largest;//表示最大元素，也就是根.5 Z9 ^ r2 b# g! O; G
int temp;//临时变量，用于交换
( E2 E2 I8 `. a1 R$ i
int k;
) g8 b+ t% O9 b
l=2*i+1;! q8 }/ `2 O% t o& ]+ ?( a
r=2*i+2;
# D# b5 A( R/ n/ Z$ J: U
if((l<heapSize)&&(A[l]>A[i])) //如果左孩子大，那么记下下标
) u3 G7 ~+ c, v6 I. L# a- Y9 L
{
' x: |) o q4 k8 I4 ~
largest=l;. G- {; `4 t9 `& p9 I
}1 ?+ @# H/ \% U' k4 ^
else+ x* L. r7 |" P+ v9 m" J. y0 O
{
8 S% n3 m% U8 u; I/ O/ @ V2 {2 ^- ?
largest=i;
5 m0 D* {: ^" i+ x9 Z
" f# I3 Z) g- ]2 F
}6 |! V. N; g( P q
if ((r<heapSize)&&(A[r]>A[largest]))
+ |8 D. L2 H& L. W
{7 g- K+ E8 ]# ^4 o0 n. G
largest=r;
- e4 G( X+ I5 J- h3 ~
}
4 O! ~$ p2 M1 M5 [ |$ ^
if (largest!=i) t& B) u1 W0 o2 j5 C. k/ w. T
{
# s. q# J4 ^! X0 i6 v, G
temp=A[i];' V' t' C1 j3 ]9 l9 j& m
A[i]=A[largest];# M/ N+ M5 U8 f$ V, {1 \
A[largest]=temp;
- u3 W* F% i1 J' B- ^) O+ A2 l
//递归调用
X& D/ y3 y4 r" N' h8 j
MAX_HEAPIFY(A,largest,heapSize);! @; J) d l5 Y. i3 a. S5 v
}
6 {) P4 o' t, | }! D
6 w1 a/ L6 \3 c" {5 J
}. L; `4 N( e4 C3 s7 b5 [# p% a+ _. Z+ p
/ v! `% N$ K2 g' ^% { n
//建堆8 { s. f# ]$ i2 i5 c% P
void BUILD_HEAP(int A[]){3 _9 w9 p" e& i a2 g' O
int i;' T+ d: P4 T6 h5 v
for (i=N/2-1;i>=0;i--)
* r: v& Q0 P! ~; L) e1 C
{
% I3 G' [" G! [5 m, j7 b' }$ {" q/ M
MAX_HEAPIFY(A,i,N);6 m7 C7 b, Z7 o. Z s
}/ d3 K. }( E7 @" y; k/ ~
* m7 a6 n5 [) h
}! g& s; \: t3 v# p( O& o! C3 Z
0 ~. f- q3 F+ \" z6 J& ~# ]
//堆排序
. {* G" d/ ?* g
void HEAP_SORT(int A[]){
& s5 K2 ]2 {& d5 ]4 E
int i;+ i# J: }( G0 F+ D" d: K% N {! g
int j=0;
: m1 K( X) U- l+ H- w
int temp; //交换时用的临时变量
- C/ X1 d( D+ g8 i3 b* \: e9 ^
int size=N; //size代表元素个数
1 U$ ]' m( x% i/ f+ O- |
//先建堆5 d, z& r# d0 [7 [7 b8 d: {& j
BUILD_HEAP(A);
, z# s. l- @0 N/ Y8 t
for(i=N-1;i>0;i--)
% c$ ?/ H. L& L2 m
{7 `/ Y# t* C( @$ v8 |6 Q1 g8 @
//因为根节点总是最大的数，我们每次把根节点换到相应位置即可实现排序
; m3 k& N2 z: I
//堆排序的时间复杂度为O（nlgn）
" H# y R( s6 u, ?7 Q1 o* B Y
temp=A[i];5 h. @" n# r% l" v& V/ v5 S
A[i]=A[0];4 e( o! D" H" o G6 d/ H
A[0]=temp; c: b9 |& q5 w$ d# Y
size--;
8 k: G+ F0 `: s2 B
MAX_HEAPIFY(A,0,size);
/ O# P$ Z! \* I
0 K; G$ ?5 j$ s1 ^
}
- g) ?8 q3 z* c5 h- p& {9 v
for(j=0;j<N;j++)# P' P2 K* [, @: W) N& s/ E
{- o$ i# ?* `' b) L9 f8 O8 a0 R, N% E
printf("%5d",A[j]);
# j( s$ ]0 D6 C! ], M4 |
}5 m9 q& O" _% J1 e9 X Y2 \! q
3 E+ [) v2 ^. U2 ~4 f/ {5 t
}
u! ]" s9 H8 ^' @" Y
void main(){8 j" I, K1 P/ M7 g* W3 p0 l9 ]
* O7 |5 \5 k3 _- ~$ U
int rand_no=0;
9 B& P2 f3 T, R
int i=0;
5 [: G) R0 ~0 U$ `
int a[N]; //n表示数组长度
! w! Y0 y, f4 K- i9 a$ @* Q
srand((int)time(0)); //设置随机数种子: K/ |- k! m6 H2 c; p& a
printf("==============================排序前=========================================");
4 c" q% i( n$ x& `; _ U
printf("\n");
, K4 v r- ?, p4 `$ i
for(rand_no=0;rand_no<N;rand_no++)& x8 R8 M4 f. M1 O" s
{ B3 z5 L V+ m4 s) {; h, f( Y3 O$ Y0 \# a
1 A b0 p8 S; p: T
a[rand_no]=random(100);
! g! W$ i: f2 n4 `! u+ D
printf("%5d",a[rand_no]);
8 _" T+ a1 J& Q* `+ O
! w" }% n& R# }# {1 l
}! p+ v/ @( P y2 r5 e/ i( q6 i
printf("\n");+ J: `- c+ D: G; e
printf("==============================排序后=========================================\n");
- G/ _6 R2 k$ ?* }7 R; n5 E
HEAP_SORT(a);& r* N5 v, l7 u4 {* F6 O
printf("\n"); , { q5 s1 P# g
, k. e, `- p' }6 Z4 S2 U& f8 K, J
7 M- S1 P+ h7 P: j9 k1 W! q; M* z
}7 F9 C+ r: n+ Q0 p. O2 A

复制代码