【转】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>! j7 ~5 P! @' {; Q$ B5 a
#include<stdlib.h>
5 J% D) j4 C; m
#include<time.h>
) Q5 t) k' J. {' X) M* W
#define random(i) (rand()%i)
% n\" l; |7 H3 q- n, L
#define N 15
4 F& f1 o\" ~4 W% B% N. }: Q
) s _+ c8 O3 @! C# m
//维护堆的性质，这里是用的最大堆) I4 _+ Q# V7 W+ s' b\" ~
//且为二叉堆
+ I3 O+ d, F- `
void MAX_HEAPIFY(int A[],int i,int heapSize){
j& I3 @& h- V' o1 m: p( @( R
int l;//表示节点i的左孩子6 u6 X% ]\" e+ ~, b' u\" m5 K* G
int r;//表示节点i的右孩子 {/ b( Z4 N8 O& T: g
int largest;//表示最大元素，也就是根.6 V# n( t2 {# j' m9 g1 V& O
int temp;//临时变量，用于交换
/ r) @+ N6 K& B) S9 m% X: @0 [
int k;
) L) U0 @- G1 z
l=2*i+1;
+ @1 n7 @4 M$ Y* S* B\" O# U
r=2*i+2;
: u% W7 K' d% z2 w4 Y% w ?
if((l<heapSize)&&(A[l]>A[i])) //如果左孩子大，那么记下下标
; h8 K. P/ g H: I7 }6 i! T( H: H
{: R& U* j/ _! Q6 D
largest=l;
' F1 v: f! V- A$ G: t3 H
}
6 n6 T: d5 [3 ?1 V7 G+ I
else# D9 Y% E- y& Y/ K% ?2 l\" V
{
( _% a# V: i6 p7 ?
largest=i;* \0 @$ v/ W8 p0 b
- t5 _' J Y2 b; ?\" I4 z2 {
}- V* v6 X' I7 Z; s$ G2 f7 s, ~
if ((r<heapSize)&&(A[r]>A[largest]))8 G2 ], T\" E/ S
{6 `\" Z; e' Z ~- a; z+ O
largest=r;
# r. L5 O! K2 l+ {
}
4 a$ d( |# L5 k' u, e) n) c
if (largest!=i)- R, B* E1 H4 ]
{
\" o+ W1 D7 [6 m+ H
temp=A[i];/ x* Z+ K- W4 b. I0 }
A[i]=A[largest];
1 e8 p# s5 i+ T: Y2 R
A[largest]=temp;6 S6 y1 a, a7 {9 r/ T& {$ E4 w
//递归调用
5 ]. G5 y/ Q5 ^: T
MAX_HEAPIFY(A,largest,heapSize);# u1 I* J! Y/ r2 Z& `
}- h0 Y' `/ i2 r8 V
. u5 ?5 N L2 c X8 u& [
}\" [3 p3 s3 }* z: \( l# @8 Q8 U
6 `$ V: @9 u+ L
//建堆* s: T4 y) g\" ~4 o2 K
void BUILD_HEAP(int A[]){# O& k7 _7 w7 z3 ?3 o/ x O
int i;
\6 |6 [1 m* z+ D. H
for (i=N/2-1;i>=0;i--)) J' v i2 d8 q: q
{
: P5 g& D4 B\" V% v9 i0 a
MAX_HEAPIFY(A,i,N);. x! o# u! }0 c! k D\" P
}2 U# \7 Z7 }; b- G9 H7 {
O. p, K C, g! F/ F( o0 `) t
}
- L7 ~/ c# r( e6 e0 I8 ]! E/ V& ]
0 D4 X$ Q' P1 V6 c2 G\" [
//堆排序8 G1 e2 s+ a& v- ^2 B, H2 T/ T' Q
void HEAP_SORT(int A[]){
8 x+ r, B- W1 i# L7 A
int i;! ^; F4 r% o\" l- p% r
int j=0;
0 F4 W8 w+ Z8 u! I
int temp; //交换时用的临时变量
. S8 z, l' g( ?\" E- s L! o
int size=N; //size代表元素个数
$ W# ] J; Z$ z& k; V/ q
//先建堆9 [\" P( i* S. r+ d
BUILD_HEAP(A);
for(i=N-1;i>0;i--)9 F A- i y$ u7 E& V5 P
{
! l' L& P: w/ U\" U- `' U$ I5 @7 v
//因为根节点总是最大的数，我们每次把根节点换到相应位置即可实现排序 ], ]\" b1 t6 |\" g5 |
//堆排序的时间复杂度为O（nlgn）% P- d8 T q4 H; X
temp=A[i];
/ {\" O. j s7 f) [& t
A[i]=A[0];( {0 u+ I+ a. B9 |$ M3 K
A[0]=temp;
% W2 X# Y4 H5 }& J G$ p
size--;6 q% Q\" R\" }/ y) n4 V\" C7 x2 |\" v
MAX_HEAPIFY(A,0,size);/ l+ V; ~. Q0 F
?& y: T7 F$ [
}
8 c, _( I6 g' m0 _
for(j=0;j<N;j++)
: k* A& H% G, }; M! v6 V; d
{
! _, g- p\" J% K! E8 W9 @3 @
printf("%5d",A[j]);% d4 E& m5 ]+ x. Q$ V4 }9 m; Q
}
8 s- L( W( V9 @
) W7 \/ o2 `3 Y( f- Y1 H+ y4 D
}
. E% y\" p2 U9 f. c% {* |\" M
void main(){$ G\" G, d' m8 r9 M$ E' ^
4 y+ d B3 \6 X; d: `9 l
int rand_no=0;
9 i3 B9 j2 C1 O$ p; ]4 Q
int i=0;
! g3 M7 Y3 b& J# g! x- o
int a[N]; //n表示数组长度
2 ], b3 Y- y3 @3 o( P- s
srand((int)time(0)); //设置随机数种子
& W\" U# T$ f! R* k; C
printf("==============================排序前=========================================");
4 D+ Z( ^$ x( N, N) j8 K! ]
printf("\n");! ^8 d1 E2 h+ j! g1 p4 I
for(rand_no=0;rand_no<N;rand_no++)
3 Q. @4 D2 i3 o! L1 P c1 q5 ?
{
8 f6 q$ u9 U$ h: t0 B
6 I, v e% H8 ^$ \
a[rand_no]=random(100);8 z7 M0 a# `' v2 T
printf("%5d",a[rand_no]);, s F% |1 L. d9 ?9 X3 N. }
. i' |% _7 V' U1 v) Y. [! J# F
}! q4 r. V% \% p( S) [
printf("\n");
3 f3 }, f3 g* Y9 ?* n4 J8 T! ?3 u
printf("==============================排序后=========================================\n");2 C( h0 k! r! `& K. j/ }5 m6 x6 d
HEAP_SORT(a);$ K, K3 P) `/ R. V1 D8 d
printf("\n"); 7 z2 C8 w4 t q9 U3 R
1 F& D# ~% s$ a
3 v, Q1 g. P( t* v6 g0 Q
}, b) i2 D2 F3 O! _6 N