【转】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>
$ Z+ ?$ L, ?6 \8 ]% x
#include<stdlib.h>& ?! s. f4 z1 @4 c9 l' F- z
#include<time.h>
7 P0 M) y9 F: K$ x
#define random(i) (rand()%i)- k4 P# m0 O# W v$ k
#define N 15! \3 ]8 |: |5 M/ w1 O1 b
3 O. ]$ x: l$ U0 _; y g2 G8 W
//维护堆的性质，这里是用的最大堆0 }9 D\" i+ J+ W* D5 k: Y
//且为二叉堆! |8 C# i4 K# Q: x( w. P
void MAX_HEAPIFY(int A[],int i,int heapSize){( G% a% X$ [- E+ f3 @
int l;//表示节点i的左孩子/ O1 N/ Z, o2 Q5 C( {
int r;//表示节点i的右孩子
) S- I\" r+ F, Q$ O% [$ ?
int largest;//表示最大元素，也就是根.
. w8 w! V w2 g1 k
int temp;//临时变量，用于交换
/ R, }2 Y/ W/ w$ J0 h, M# i
int k;% C' N# t/ s% i# m
l=2*i+1;
, n! o4 w& b: B' e
r=2*i+2;
+ G# @+ l7 `3 P1 p( k
if((l<heapSize)&&(A[l]>A[i])) //如果左孩子大，那么记下下标: Q: K; H7 l B( F$ C
{7 S E* T/ h; e\" k0 k1 I' W
largest=l;
- Q( ]9 I% R3 I4 ?$ K! G* o
}+ b- y$ b# ]6 \8 ?
else
/ J4 K, y( a( Q7 k2 |! `
{
8 a\" m, a# n! d8 q* L8 V
largest=i;
' ~7 g0 U4 d' g$ M4 m
' d7 x6 X5 l0 O2 c7 R! ^' O
}2 b# N) p* L, h5 I
if ((r<heapSize)&&(A[r]>A[largest]))
2 v0 M\" @: k% y _( G- y
{
8 i1 N* E/ K; G( J& w* z
largest=r;. ]\" O+ A( P# M
}8 R) X7 o: Q, m$ t4 l
if (largest!=i)
# U( C. |. N) R& G8 R) s
{
1 D! ^6 ?! h. z% @0 F/ {' E A
temp=A[i];
4 o2 v( {\" r8 N2 D% n/ F
A[i]=A[largest];
\" I$ C+ Q! h# ~! B5 C9 w# o$ k
A[largest]=temp;% C9 l+ ]+ B4 n: d9 S- Z
//递归调用9 j8 g$ I( `' Z6 H
MAX_HEAPIFY(A,largest,heapSize);$ n8 F9 M* q0 N$ n- |4 v
}9 q; F( x) N$ ]! H2 O; C& g* |
, h9 `2 [. X& {4 ^8 t
}
$ t\" ]( b- Y) j7 B, ]$ G
! T6 v. u0 f; m1 ^+ i& t* c
//建堆\" z$ [: `5 u) {& c* X, q
void BUILD_HEAP(int A[]){
d( k2 y1 B$ N8 O5 G+ r
int i;
6 y' j7 v# _/ A2 w- l7 b
for (i=N/2-1;i>=0;i--)$ I: ]3 t2 n1 ^
{7 o* w/ W6 ?0 d( @9 S3 m, |
MAX_HEAPIFY(A,i,N);
7 T; e/ }5 C# _8 C. K' d4 K
}
# B' h; f8 q8 N1 D& R! a3 L# q$ {
3 c9 E, u, A! l. z
}
( s- \8 \1 z\" E/ K. ]
- E2 z' i! V' `! s- z* o( ]& H
//堆排序
8 N# N6 w& b# s' J
void HEAP_SORT(int A[]){6 `6 A, }* J. l* H
int i;
; J+ x& H, j4 p& Y3 C
int j=0;- ~) |' F# U* ^7 E1 U\" I
int temp; //交换时用的临时变量
3 t) K) I0 L, p; h1 f\" ?
int size=N; //size代表元素个数
6 m' [1 s3 Z8 D7 D
//先建堆- W: b# m/ {9 @
BUILD_HEAP(A);# _/ v1 f9 i& ~8 e8 f+ q8 C G; v
for(i=N-1;i>0;i--)/ A2 ?3 x7 V6 @$ y\" P0 E' f\" Z/ A
{
# q. v0 }; e g7 M2 z) T$ t
//因为根节点总是最大的数，我们每次把根节点换到相应位置即可实现排序, {) r' Q2 w( g# X0 S1 H
//堆排序的时间复杂度为O（nlgn）
* L7 y1 j$ G! M- o% a9 X: l
temp=A[i];( O% }4 n' q Y/ [
A[i]=A[0];
9 Y6 y( b h2 r1 H3 U( G9 A1 w
A[0]=temp;
+ R8 V7 L' f; [: u- U- {6 O' E
size--;
1 k6 S6 @! O; T/ c
MAX_HEAPIFY(A,0,size);6 F0 Y) U$ n1 X
3 Z( Z$ D2 t/ ~9 _# ]4 s
}0 g: c0 v- T8 W0 ~0 ?& M
for(j=0;j<N;j++), ~\" ~7 q9 j9 I* r4 m7 G
{
: ~) P+ E' ^; ?( H- F) W, P
printf("%5d",A[j]);
+ a) M0 _. I7 O }
}
( g3 s\" p8 F$ M& B) `: a g
6 U- J& [1 m% @; `
}% Z3 u3 q5 D$ [! @\" ?+ ^
void main(){
) I+ t9 R$ E9 ~4 Q# \9 ^
& j' ?: r: J\" M! b1 J; S! y\" i5 R D
int rand_no=0;
/ a- m q6 ]2 y B/ ]+ `
int i=0;8 j9 a# D9 ]/ D
int a[N]; //n表示数组长度$ F; @6 w+ r4 }( l, `! o) F
srand((int)time(0)); //设置随机数种子
1 ]! k/ x- H5 V& c
printf("==============================排序前=========================================");
2 l. q, S6 W0 I& G
printf("\n");4 y$ x* l7 S8 ~! R# ~* o
for(rand_no=0;rand_no<N;rand_no++)/ R% o9 n) H7 [! W8 y2 P
{3 o# p& i9 t$ C0 {) h7 {\" H+ P
8 q; u, t4 ?2 d( m& H3 i& @: k
a[rand_no]=random(100);* G5 f4 F( l B, C& _# ]
printf("%5d",a[rand_no]);( P6 N. n& _' n0 c
: X, {3 ?; u) Z' @4 n! H
}
8 z; t8 R/ t, K/ |6 [' m* R6 j7 ~
printf("\n");
2 g2 s( b( N5 [/ r
printf("==============================排序后=========================================\n");/ t$ n4 X8 R# Q9 j! V
HEAP_SORT(a);
/ H& M+ V* W1 m8 e7 \7 s\" I
printf("\n");
2 `5 ^$ I# W3 k! Y/ k/ `. p( [
, u( d0 Q9 N$ ~ ] U# p
5 _0 A4 {4 c3 }
}
$ u- P- ?0 O- Z' V3 ]\" j2 h3 d