【转】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>
\" l+ ~7 |* X9 z+ w/ }( b! J
#include<stdlib.h>
6 T) H4 Q. f/ U5 ?: L4 v
#include<time.h>
! v6 i, F# n) F
#define random(i) (rand()%i); `' l% f7 t: n6 ]. O\" Y
#define N 15
9 W\" [1 V H; Y2 Q& N& P0 \. `
( B3 ?& ?/ }7 ?\" o j
//维护堆的性质，这里是用的最大堆
8 T) s8 }* u' C2 z+ X _
//且为二叉堆
# a7 H: R% }: ]5 F
void MAX_HEAPIFY(int A[],int i,int heapSize){
7 H: a/ i$ ~, ]. z
int l;//表示节点i的左孩子& I9 }- H\" N5 ? V\" J4 m3 Z8 T4 @) ]
int r;//表示节点i的右孩子( n+ \8 ]( p- |) J( O
int largest;//表示最大元素，也就是根.
9 q# Z: Z) z# M2 L! V
int temp;//临时变量，用于交换/ i( @3 h; J+ n# p; Z
int k;$ A, `* Y: j+ r
l=2*i+1;. n1 Q8 @0 g C8 r2 n/ o) i; k
r=2*i+2;' ]$ _& G; r+ i. I
if((l<heapSize)&&(A[l]>A[i])) //如果左孩子大，那么记下下标9 u- x% |# `) w7 o0 x- a) X
{1 G; Z; a, {9 v- C1 b0 W. U' _
largest=l;* L. J3 o+ F+ }& p: Z& H- }: S
}\" L' W; J' P) m( l1 d) D/ ]
else
0 ]' }+ H' T3 d9 t6 u
{, N0 a9 _, L, }/ N
largest=i;
; e/ d3 d; A' a
: P\" w# X5 p# G
}$ O+ C9 d$ D$ f( O' I
if ((r<heapSize)&&(A[r]>A[largest]))
$ @0 K. R% e3 }. t4 ^; K) q8 m
{
' H2 Z\" L9 K( o+ M. p5 }
largest=r;
\" p F; }; c1 S
}0 O- T8 O! M0 K) D+ ?: Z- s
if (largest!=i)1 Q, ^1 I$ ]( ]' N4 d
{2 v0 A5 a8 c( x( h
temp=A[i];, \( N7 i3 y3 l8 e6 r5 ^! }7 G
A[i]=A[largest];\" u# r$ e6 o# P
A[largest]=temp;
//递归调用
2 {$ o+ W+ F\" y, Q& w2 n
MAX_HEAPIFY(A,largest,heapSize);
6 {1 s/ M7 ]3 k' x1 k
}
2 j: w' [1 m! `3 n. p
; b' b/ g+ ]7 v0 |/ D
}1 Q. E& I% C2 }9 k$ q
( U( l; I8 E) l\" |4 g3 Q
//建堆$ u8 c( y5 |% x) O/ v
void BUILD_HEAP(int A[]){; r+ |% W) G8 N: x( {1 C
int i;: s# O8 T! x1 \$ P* d
for (i=N/2-1;i>=0;i--)
/ p* `2 P b! P: e
{$ G0 n b+ J9 M, E+ {$ ~$ _
MAX_HEAPIFY(A,i,N); r' T0 r5 _\" y$ F
}
/ T: m) W, c. F0 \; N
( ?* [4 { k! x* O! h& i1 P
}
0 A( C- |* ? p* e7 O
) q5 d% s h# e i\" @
//堆排序
9 M- v& E. ~. n: N0 r
void HEAP_SORT(int A[]){
$ W\" w' c% A* a$ U5 q: ]
int i;\" V& V- a! k- l/ L! Q( D
int j=0;8 v! g# _5 M& u0 o6 Y
int temp; //交换时用的临时变量* x7 }# @9 a9 g
int size=N; //size代表元素个数$ R3 a5 ^( x8 m! T% _
//先建堆2 o3 C0 u4 K6 }9 |0 d$ J9 l
BUILD_HEAP(A);
\" K4 `$ r3 }- U
for(i=N-1;i>0;i--)
9 A\" n# c% [6 C4 J0 z- \
{
6 _# x2 o Z+ J$ ]% \8 d
//因为根节点总是最大的数，我们每次把根节点换到相应位置即可实现排序3 B9 g3 }% v+ }- o
//堆排序的时间复杂度为O（nlgn）3 ^- k- C; m0 S8 s+ `) Z
temp=A[i];
6 b' W) r: ]- t5 }5 t& `
A[i]=A[0];
$ \9 t3 c$ E) L) U
A[0]=temp;8 `0 ?, S$ I: k' d' {( u
size--;
: U7 {9 ?; t2 r# c
MAX_HEAPIFY(A,0,size);& `) t1 B/ ]8 b1 i# S
+ X* L- a. F# m; V6 {, T# D* \
}% s# E2 o) }7 n, S9 K6 |
for(j=0;j<N;j++)/ I( L; _8 m$ L5 |- L
{2 `4 k- S/ c1 r
printf("%5d",A[j]);
6 Z8 b; ^& R1 ?1 m0 H; }4 l
}
/ x7 ~9 R: C. F7 U7 o3 S- [
& B6 b- g1 j; U; B
}# ~, m U* [/ M; D3 _
void main(){# G/ m. t f\" _9 K
; M\" B% r% c# J
int rand_no=0; K# K& ? u2 c& L( `
int i=0;, Z% W3 V9 D! a M8 a* v, s }& D) N
int a[N]; //n表示数组长度
\" `& i: B! K* H% Q- {7 R4 |* Y
srand((int)time(0)); //设置随机数种子
# t F7 ~; {* E
printf("==============================排序前=========================================");
9 T$ ^6 m5 F\" Q+ q7 Y\" h9 S* n
printf("\n");\" J [9 g7 n3 Z( u\" j! c2 `$ k
for(rand_no=0;rand_no<N;rand_no++)2 W3 O! R- q6 h p2 B5 I
{' ?4 E. f9 T6 p, M. M9 _0 t9 N
' X! a9 m- I3 _1 r* k8 g7 @
a[rand_no]=random(100);2 S+ z6 d+ r3 a e. w- N' }$ B% C
printf("%5d",a[rand_no]);3 A; l& o6 q7 [! ~
2 Q6 ]. R; X; [: K8 Q! J
} r' o6 b, ?; t' [+ G
printf("\n");; x5 x/ ^3 T1 {' z, X3 h+ U( a: R
printf("==============================排序后=========================================\n");
6 j& j9 E$ Y, |* ^; t! P7 _
HEAP_SORT(a);7 N/ u) c7 P B2 c& S J1 W
printf("\n"); ( _% `- f4 z% h6 O7 I A- W
/ X! s3 F: ~2 s
6 f( G! t( x( O& m2 l- t
}4 [4 B7 L# ?, p! p5 d* U2 G; \6 F