【转】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>
- p8 | j: w9 | h
#include<stdlib.h>; }. j1 h4 c3 Y) S) ^6 d
#include<time.h>8 A# h [! B% t
#define random(i) (rand()%i)! d. w C- v1 M% ` W! v# W
#define N 15
+ O6 [& ]1 g. p\" A$ T: K# k# p, R
! i' j1 f4 p u7 D
//维护堆的性质，这里是用的最大堆
- m# `* x- V0 n
//且为二叉堆
8 ?( l- Y+ O1 g/ Y0 V# B1 V) a. E1 x
void MAX_HEAPIFY(int A[],int i,int heapSize){
- _, x+ G1 E0 a5 w ^0 H
int l;//表示节点i的左孩子
6 m( \! j: K: z/ }3 I2 J
int r;//表示节点i的右孩子
9 j+ s, t8 L/ ]; v. S
int largest;//表示最大元素，也就是根.
, n, v N, _( H6 n \/ L/ F Z
int temp;//临时变量，用于交换
/ F& o) S4 o1 q7 m2 A
int k;
0 f% P+ z9 @) s6 G7 _1 D( x' s
l=2*i+1;# i t$ l2 s* W: B
r=2*i+2;
$ y y& F# d/ r
if((l<heapSize)&&(A[l]>A[i])) //如果左孩子大，那么记下下标
0 B1 y( Z0 U8 [# T9 k$ B, n0 ]1 ]
{
' B* ^1 n) V0 p R
largest=l;
9 u/ W) j Y2 h4 {: g- x5 k
}: D1 r& [3 y0 B$ \6 T4 D) T
else2 U9 k! ?; x) {# P
{# f1 S& e$ _: Y; f( A\" U- F# S3 Y
largest=i;, c( v+ F/ w$ n$ K* |
8 S& Y( O2 e* _
}
% w: B8 _: B! |% |
if ((r<heapSize)&&(A[r]>A[largest]))6 l% P\" D) \$ \! \$ y
{
% n# t3 J l: s4 m8 }
largest=r;
* a7 c- u\" b* q( v! Y3 H
}, |: b/ \& O* P) ?3 ]! P
if (largest!=i)8 }/ n- n4 S3 N6 p0 y1 M
{
5 u; q4 Y/ n6 V% [2 x( I
temp=A[i];
\" r: j0 p' |2 S
A[i]=A[largest];
$ h U$ N. Q3 l6 ~
A[largest]=temp;
1 @3 p4 c5 R2 w% \1 q4 P: n! O
//递归调用 ]2 E2 @4 f6 n0 \9 M* C; u
MAX_HEAPIFY(A,largest,heapSize);
+ s) S3 _$ B; S; _& F\" R
}
+ z: I( U- ~% E1 Y9 V
( u' B/ L8 @ r
}$ ~0 c. z2 p+ J, K
9 G$ v1 X' f\" @% u\" e4 @/ ]0 ], \
//建堆
& Q+ w! i& _% \6 S3 A
void BUILD_HEAP(int A[]){
/ M8 n0 J/ [+ y9 ~
int i;
# x6 ^3 \! i) T& e1 o+ Q
for (i=N/2-1;i>=0;i--)
' Z\" q$ e) i# h; B
{ W+ Y6 d* }5 L) f2 d8 b\" A
MAX_HEAPIFY(A,i,N);
( {+ ?1 C& A) M# E
}
1 j- n% t2 E9 N |/ [( V
* c( O2 f- e4 ?
}
' m& h/ z) @8 e4 ?# u8 h3 P
( l7 I6 w: P/ s
//堆排序
; y I# ]: O3 D% y\" s& L
void HEAP_SORT(int A[]){
+ X0 q0 X3 O- c3 ?$ y9 _, E' a
int i;
! E! i4 I0 p- [% D- s0 c
int j=0;9 b y, z+ c% F9 y
int temp; //交换时用的临时变量
' B$ T# S% e+ Z9 Y, _2 M
int size=N; //size代表元素个数6 z% g- U\" x\" \
//先建堆
# b1 e) k8 R5 l6 g1 N( D! W
BUILD_HEAP(A);. H! @$ ^5 q) Y6 y. C8 c- r\" h/ U+ k
for(i=N-1;i>0;i--)
* U* {% m9 f\" H7 Z# h% z
{
. }6 H4 D5 x& R
//因为根节点总是最大的数，我们每次把根节点换到相应位置即可实现排序4 `7 Y) u) E: Q\" \ V$ a6 B
//堆排序的时间复杂度为O（nlgn）' l5 d+ u* X3 o6 w
temp=A[i];- l\" F3 w1 I) r) [/ Q) Q. y
A[i]=A[0];2 s- x! {8 ]0 B+ R3 C: d! c
A[0]=temp;9 |\" d$ p8 b, F
size--;
MAX_HEAPIFY(A,0,size);
9 [' J: `! l6 `0 S' n+ Y
0 r& I0 {' b) f: a- ?
}
4 U4 ~3 v* B' C/ J% R
for(j=0;j<N;j++)
6 G1 @* ?0 v: X* R5 [5 y
{
# H8 g; L\" L5 x
printf("%5d",A[j]);, G6 A7 q. I( C! x/ R: r& z
}
: J; Q! C, \\" | R* z. I5 q
: c% _; o) B% ?# [, [2 h a( S
}* d' c+ P( k; w3 h: j8 t
void main(){
! j. X- c1 ~) w7 |
6 O0 t; x, Z3 n- B; n' g
int rand_no=0;
& U3 B& [$ T% C
int i=0;
3 O/ h, S- [3 f+ j
int a[N]; //n表示数组长度! U4 J/ J. H( [; E, N$ z
srand((int)time(0)); //设置随机数种子9 x, I$ k& n8 W2 f- Y4 Q8 R; `
printf("==============================排序前=========================================");& b! @; V6 [/ K- E8 p5 ]
printf("\n");3 U4 {( X$ S R% P1 I
for(rand_no=0;rand_no<N;rand_no++)
+ t% S9 D! B( [# B9 D* J
{
9 }$ a# U7 e; }+ e% Q0 _5 E9 \
a[rand_no]=random(100);\" X( T# k- r! N' _ N
printf("%5d",a[rand_no]);
1 ?% a7 n4 h6 A\" o( w
8 Y, K1 v/ W7 g- k; w9 M4 I
}
4 G# l. L+ H) S$ S: {
printf("\n");
2 i5 k1 H7 q! U- l! @) Y
printf("==============================排序后=========================================\n");
3 I! X) [# v! v% L5 K
HEAP_SORT(a);* f7 e$ M7 D* s9 J
printf("\n");
# R( e: f& f9 t% ~\" ?/ _
\" }; X, n0 _: u
7 L+ v' D. m! h8 w6 S
}
3 {- y& n5 Y1 \6 _* F% Y