【转】c语言版堆排序

[复制链接]

字体大小: 正常放大

wangzheng3056

937 主题	117 听众	3万积分

升级 0%

TA的每日心情

	衰 2020-10-25 11:55

签到天数: 264 天

[LV.8]以坛为家I

自我介绍: 内蒙古大学计算机学院

群组: 2013年数学建模国赛备

电梯直达

1^#

发表于 2013-7-31 12:04 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

#include<stdio.h>
3 ]% y1 P: K$ y b* }; R; \, n
#include<stdlib.h>
, b8 b3 h& ^5 l y9 X
#include<time.h>8 h0 D0 e* m/ i
#define random(i) (rand()%i)
: d\" {5 [' N) G
#define N 15
4 Z- {% [3 ?2 E* \6 \
5 P9 i$ o- T* ?% c x: t) p5 Y' n* |- w
//维护堆的性质，这里是用的最大堆0 z4 i2 T9 u0 A; d5 J8 O1 s
//且为二叉堆! [( m s3 C3 K2 m& }
void MAX_HEAPIFY(int A[],int i,int heapSize){
$ q f6 f7 x6 S5 n1 {0 Y$ U
int l;//表示节点i的左孩子/ L% a v\" o4 {* B
int r;//表示节点i的右孩子! r I; s, L, e- X/ \
int largest;//表示最大元素，也就是根.
, k6 ~8 D5 T2 r/ u L
int temp;//临时变量，用于交换
3 K5 h2 q# x I' S% D4 n
int k;0 }\" Y* X7 w/ \' h
l=2*i+1;3 r8 W* ` v. N5 z
r=2*i+2;. E7 j1 d7 }2 n. ^% }
if((l<heapSize)&&(A[l]>A[i])) //如果左孩子大，那么记下下标2 T( [9 j\" n* I* `9 _5 o
{6 W: [; s7 u4 K7 {0 t5 R
largest=l;
1 O( R4 f+ U2 p6 y6 Z3 @) w
}
- R4 t/ p7 _$ ]) U& @/ W) _
else
B+ k! a+ ?9 k( p9 ]
{
( ^! l- G5 Q3 m7 h$ v
largest=i; y( m$ P& l3 X$ y
. l+ I6 B( `( b# _% Y p
}: ?, N& n: Z+ K* \9 q
if ((r<heapSize)&&(A[r]>A[largest]))\" ], p: s R1 V8 {- c
{
: V2 y5 E/ d- v% N* N, c5 Y
largest=r;
w- r6 A' ^- x3 L! ^1 B* U
}' F1 H# B\" x+ v: s$ X: H. h
if (largest!=i)
2 R- q: Z- K; c' J
{5 j. C1 d1 _/ }2 k
temp=A[i];
. k# P: ]& X4 ?8 }+ _1 j
A[i]=A[largest];
) X5 r* c# Q; t, h/ `. x6 G
A[largest]=temp;9 I4 j+ d. [! C2 B# w' w
//递归调用+ p. S+ r, I: J; U2 D+ h
MAX_HEAPIFY(A,largest,heapSize);( ]9 |8 o' S# c
}
% F$ Q\" S. F$ a+ S7 p\" g; }# w
8 X8 g% f( [0 v+ `
}. n# q7 E& k: S6 l3 v
7 M' f3 a( ]8 U: A7 r5 o
//建堆6 R' Y/ [# Z) B\" D! T
void BUILD_HEAP(int A[]){' y) M6 u2 p5 U8 ]2 e5 b
int i;4 z+ b7 g1 C( H* b' g
for (i=N/2-1;i>=0;i--)1 k- R/ r2 }! v
{7 J+ l\" `4 _. s
MAX_HEAPIFY(A,i,N);
- K1 t# j6 Y5 O6 L. _$ `! k( k
}5 Q% s( c9 s& R2 @% e, N+ w9 u
6 Z! p9 ~6 u( x* i1 }6 ]! f
}
1 b+ R# a5 b6 ]2 \
@. o: r) q+ q7 E5 `& K& ]
//堆排序
' V# ?( Z) R* _, `
void HEAP_SORT(int A[]){ o4 V* ^; p4 y\" [: a1 y7 ^
int i;
1 n6 B& T/ Z( k7 E6 G7 J
int j=0;
B3 ]4 o) \\" }
int temp; //交换时用的临时变量; Z\" ~- c6 Q6 g5 p( t8 R0 v
int size=N; //size代表元素个数$ L\" n3 N7 k8 L5 f; {, j) d
//先建堆
7 E0 s7 a7 g* `6 x; N; x
BUILD_HEAP(A);7 @4 a% O3 [- G\" {8 ?
for(i=N-1;i>0;i--)
& F' \9 P k7 z. w
{
5 j s' ^. V: z4 v6 ^
//因为根节点总是最大的数，我们每次把根节点换到相应位置即可实现排序; H6 H, [/ Y$ k! ^* }9 v7 @* r
//堆排序的时间复杂度为O（nlgn）
$ h& q3 K* w- |5 Q) o. U5 y; z! o\" A
temp=A[i];
6 h: r+ J, H, B! f- W- B8 {4 |
A[i]=A[0];
8 x# D& d b0 }
A[0]=temp;1 ~' s) \+ d# V
size--;( v3 w6 B% i9 T! ~5 [& J4 Z
MAX_HEAPIFY(A,0,size);! H& [ w# I! r$ A5 Z
. E# q! e3 I: R
}\" T2 w3 O0 K, z; G
for(j=0;j<N;j++)+ D; I) A/ m% O B1 I7 B3 }6 F
{
/ p* K8 D( e! D
printf("%5d",A[j]);5 s( Q+ X& B7 w5 [+ R. q9 t
}9 t% k8 u3 ~ ^, x
9 b2 s4 z7 C/ X7 s, k
}
1 ?1 G$ v\" ~( D7 v3 t
void main(){
\" x/ q9 ]3 C\" W) l
8 O- M, K\" ]/ ~8 V5 p6 {
int rand_no=0;4 m6 y, `* ~0 b) v* ^: l s1 r\" w
int i=0;
! ~+ }2 S0 q$ a
int a[N]; //n表示数组长度
4 [8 [- H u' d2 q& ~
srand((int)time(0)); //设置随机数种子
* y7 `7 [/ K. J9 c: r9 P0 `# K6 h. B# `
printf("==============================排序前=========================================");
4 Q% U1 y/ O+ Y6 \5 |* m% o
printf("\n");$ n/ {; q: K1 R- |3 ~0 `1 V
for(rand_no=0;rand_no<N;rand_no++): R: x6 H) Z' A# n/ o6 p
{
* W. ^, _7 N8 v+ u' |
6 x3 o5 O, z0 e
a[rand_no]=random(100);
+ k4 t% w8 a, {5 b0 D
printf("%5d",a[rand_no]);' P& }; S& y6 ^- B* ]3 E: } Z
3 l$ C8 j* X+ [
}
* U- l3 X2 F# ]/ c, ]! J! V5 _6 [
printf("\n");9 _0 I. w* G9 F- M; q5 h0 I
printf("==============================排序后=========================================\n");
+ R, N, x! D\" N8 z
HEAP_SORT(a);
+ D6 G; m- R1 ^) h0 a8 p7 I
printf("\n"); / l( X6 ]: @ U9 p' G# \- z* x
; M7 H3 K- ^6 C4 S5 n0 Q, B
- {$ _2 c3 @* h3 }. p
}9 U: l# |: S2 A& O\" C( d+ A