【转】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>
5 ^) J7 ` s6 o0 {* }5 z
#include<stdlib.h>
: x# _\" N3 d5 j6 ^7 m! A# X
#include<time.h> N' @ _' l$ S! x0 E
#define random(i) (rand()%i): o+ A: [4 R6 w* E# E
#define N 15
$ V4 G4 ^\" D/ q+ }: y. z
0 z; g, T- {$ E% ?7 _4 C
//维护堆的性质，这里是用的最大堆* d\" [ T+ f- ?5 z# g8 K
//且为二叉堆
) T [8 k Z& G/ i, u8 Z4 D
void MAX_HEAPIFY(int A[],int i,int heapSize){( x g9 G* S9 L! l6 _
int l;//表示节点i的左孩子
; V/ w8 ]# m1 J+ L! x8 w
int r;//表示节点i的右孩子
7 s1 k) x6 X; _2 E4 n- X9 m4 U7 K1 [
int largest;//表示最大元素，也就是根.
# J% z9 [8 Z) u' o; r
int temp;//临时变量，用于交换' j, \) K/ O) m$ `8 \
int k;& X* D: e( m\" d9 h4 J
l=2*i+1;$ {% r+ S, g* {
r=2*i+2;
- @5 _$ |0 [' g2 D& J2 G. _1 k1 L
if((l<heapSize)&&(A[l]>A[i])) //如果左孩子大，那么记下下标
0 r1 Q2 b$ E' w+ e4 N6 e1 J( ]
{8 V; O/ x9 e2 q* ~
largest=l;, o- @) E x2 i. U% V
}, R+ i' i2 B4 T) n4 B+ N2 R\" L
else/ {1 B: f5 t& J @
{3 F% S/ |) X0 k6 N
largest=i;1 u5 v+ B, u4 Z% }/ q2 h- k4 x
: t2 p8 L* D R' L4 Q; K
}- D4 T' D0 T1 |6 h7 ?$ t9 ]
if ((r<heapSize)&&(A[r]>A[largest])), V% c/ c& \/ e8 M& F$ [( i
{* Y8 N- E2 d; {0 F3 C6 X
largest=r;
, u. h# C/ j5 j& J. ?& P5 s
}) e' e7 H9 L9 ^ S, A3 h9 A2 R
if (largest!=i)/ |8 G) Q- h+ s( h5 w2 x
{
. u5 a4 m\" A) r6 ~0 b* C& ?
temp=A[i];
+ y4 N6 C% o6 G\" F/ V
A[i]=A[largest];0 h% d8 f& e2 p+ f: h$ \3 a
A[largest]=temp;
\" I( ^8 M0 F& f8 K/ Q6 L' ~ o
//递归调用
: o/ ~* z6 ~\" J8 _5 b
MAX_HEAPIFY(A,largest,heapSize);
2 m# R; z\" {! O1 G. M+ d6 |
}- l( k5 L; ?& T: ?; f
9 d- M! D; c5 c! i
}/ t( f+ ~6 W4 |$ j) |3 \
! C3 n% Z K5 n6 j
//建堆
! b6 K/ d0 j2 H8 ^( T' X3 q
void BUILD_HEAP(int A[]){
5 U# n6 r$ {; k( A\" ~
int i;' j$ {8 z h+ r9 I7 z6 t
for (i=N/2-1;i>=0;i--)/ L Q# ?7 n8 s* v
{% ?% F# q' `: c
MAX_HEAPIFY(A,i,N);
6 m2 \) D5 ^& }) V
}
- v6 |( A9 F( s3 v
' b: ` X6 }1 l) ]- J4 ^6 n
}1 R7 k' `; u Z
3 ]0 r2 g/ P$ B# A$ j
//堆排序
: H1 i) M. |: ~
void HEAP_SORT(int A[]){0 q- | Y- n8 C6 p9 }
int i;
* e( m\" w( O3 `2 c
int j=0;: W5 o( @, b/ g- A
int temp; //交换时用的临时变量
* G7 { d# r& r# @9 v Q: i' L
int size=N; //size代表元素个数
, [8 L0 X0 A\" _
//先建堆0 r' z4 Z& E2 ]* P. o: {$ [
BUILD_HEAP(A);. I8 ?8 l* w/ X8 O5 C) T
for(i=N-1;i>0;i--)
1 A9 [& |, e5 \3 M
{
4 x' H L2 ~3 w- R) v
//因为根节点总是最大的数，我们每次把根节点换到相应位置即可实现排序
- |& w' j( t0 m9 z9 N
//堆排序的时间复杂度为O（nlgn）
) O7 S: ?. Z+ b( H, O3 X
temp=A[i];
) _5 P7 K5 a( O5 Y) y& l$ {
A[i]=A[0];8 M0 P0 s- S7 U8 s5 h& ~; J
A[0]=temp;' R- p( |! L0 a# ?& |
size--;- Y# K6 } s% Q5 K! G1 J4 v' }
MAX_HEAPIFY(A,0,size);
$ U$ O. D9 M c/ g\" `0 ^
+ o5 |+ P8 {% O* y w' o9 F
}3 a5 n# n+ ?8 i6 h* w) s2 _
for(j=0;j<N;j++)
# v\" R; ^0 O8 T& [+ C' N
{) P' c& a7 H2 a7 B
printf("%5d",A[j]);- T5 s# @* X& x& @; o* c! Q
}; p, |* D+ S1 _$ ]
$ S/ n9 |/ q @- i$ k
}0 `2 Q5 I1 R f: u- v
void main(){9 K\" b; { L+ ]- \' n; t
7 i n' F9 G$ T* o; x
int rand_no=0;
8 X/ x/ h0 L; } z+ f
int i=0;7 Q$ ?\" V% Q5 m* Z8 [
int a[N]; //n表示数组长度 i$ W4 z: Z9 M\" I
srand((int)time(0)); //设置随机数种子8 l1 v. `1 d\" h$ _ E
printf("==============================排序前=========================================");- c! r8 H: R6 F3 f! G+ p; D: Q
printf("\n");9 b Q; w/ V# s/ u, b8 J9 g6 h
for(rand_no=0;rand_no<N;rand_no++)/ l% I\" T/ _3 i9 `\" N0 M$ _
{
) F* O2 F/ w/ A& s2 N# q* g
7 L! W. E* V. ~: R\" H4 f8 j0 n
a[rand_no]=random(100);
/ v5 Q# f; j9 q a\" z V
printf("%5d",a[rand_no]);3 Z; K9 F- [+ [. p
: a8 b8 W7 C' Q6 i. z
}$ u0 o5 E4 Q: g. w0 M/ {
printf("\n");
! ~+ C\" B8 v! D\" }! o
printf("==============================排序后=========================================\n");
; x, U. T7 L1 b3 {' j T
HEAP_SORT(a);) P* q7 o0 e4 v/ Q) y4 l& h
printf("\n");
7 _. H7 y+ u8 b: ~% m- R8 b E
2 F. ?, ^8 N6 w: a S
\" c+ ?0 B1 f- t) S3 z
}) i$ i! w0 ]6 j$ J8 z