【转】c语言版堆排序 - 数学建模社区-数学中国

#include<stdio.h>4 W/ t5 i& K# \% p" `: M: T
#include<stdlib.h>
* k# { M2 _+ L! d
#include<time.h>" O: o$ u# V; E
#define random(i) (rand()%i)
% u0 V" X. E- ?/ P& H( j/ H6 J2 L
#define N 15# c# h" w+ r0 G5 U
3 q3 C1 q2 u4 a/ v v' P: h
//维护堆的性质，这里是用的最大堆1 ?+ \9 a' N; F! I) q
//且为二叉堆
7 h+ Y; \7 ]5 j8 ~
void MAX_HEAPIFY(int A[],int i,int heapSize){
. `& y1 U. M0 Y, Y
int l;//表示节点i的左孩子
" I! p8 V3 T2 o* Q0 T" l W
int r;//表示节点i的右孩子
7 [2 u* @( `* Y1 x. [0 o/ @
int largest;//表示最大元素，也就是根.
8 a. }* I+ u3 B1 t
int temp;//临时变量，用于交换+ @& @8 d2 q5 P% @' o' E
int k;
8 B( e% j9 Q: k0 |/ Z/ D" A
l=2*i+1;
5 f# b% E e; N2 n9 Q4 }
r=2*i+2;- r5 v6 b! q$ L. E3 t9 B
if((l<heapSize)&&(A[l]>A[i])) //如果左孩子大，那么记下下标7 X3 Q( |, ~ j' V6 p
{3 ~, ?; C& @+ W
largest=l;
3 p" V2 w9 z; I5 e
}
; {% q3 J) c6 I1 A
else
) G5 z* V; a5 i
{
: u2 Y8 w) Z4 i5 `' ]$ \' G
largest=i;8 w# I3 c( ], r8 m3 T
2 m9 Y0 H& Y7 p" m/ K- [3 g
}
* Z* Q: b" p" F
if ((r<heapSize)&&(A[r]>A[largest]))( ]8 S" p8 y) d2 ?, f0 _* P
{, c5 ^5 g/ C% Q' n% g5 r0 ~
largest=r;& `, N* H; K7 v2 z+ S
}
7 q9 G4 {4 B4 L. l: O5 i
if (largest!=i)
7 z: i) y& c% s7 l7 {4 i9 W. [
{3 \6 d \$ c1 |# o
temp=A[i];; A3 E' d* L$ ~, E
A[i]=A[largest];
4 @$ _* [* U: E K( m6 @* ^
A[largest]=temp;
+ e- w7 Y, l4 U/ }4 H$ q3 B% u# w T
//递归调用( y. @& a3 z; D+ w* v, u, F" m
MAX_HEAPIFY(A,largest,heapSize);7 k6 `" T- b2 s
}
2 C7 s7 B8 I5 l7 q5 |
7 i6 b5 D: I; P% O9 L0 |6 c* e
}
3 I, N# Z; L! c j! m# ?
% A: S/ b% B( o
//建堆$ p% g8 s a& A: L# x$ c
void BUILD_HEAP(int A[]){
4 u& O8 G3 I" l2 k% ]$ N
int i;
, h# K; V* h- ~1 Y5 A" R1 J, M5 m
for (i=N/2-1;i>=0;i--)
5 j$ C; y$ k& x' `6 G. C2 i
{. M- |. H; X, x8 n4 @
MAX_HEAPIFY(A,i,N);. P* j& v; `- k
} u$ d+ f7 ]- f' c/ e0 W6 n6 @
5 J; n2 Q" _4 Z# c- U6 O
}
, m2 I! T( S* R4 @* L
- o' }, L* A) D" ^5 L
//堆排序
+ {& ?7 C5 n6 Y; \
void HEAP_SORT(int A[]){! E4 u7 x; h; \7 h; R- A% z$ E& n
int i;
* {, D) P i- a1 h' A
int j=0;6 ]4 U6 m: ?: k6 P8 B+ A; m x7 h
int temp; //交换时用的临时变量& {$ w3 B. a' f5 X
int size=N; //size代表元素个数
$ Z7 K, _- x- d1 a7 @$ X9 P$ `
//先建堆
$ `2 }; A0 E& B/ i
BUILD_HEAP(A);
6 ?! ?! _) K a' H/ v5 {6 P0 j9 L
for(i=N-1;i>0;i--)
' O7 ?: b4 `' @. [, C, a# I+ K
{7 ~) C) M) Y/ Z8 F
//因为根节点总是最大的数，我们每次把根节点换到相应位置即可实现排序
! B; f" ^: @8 X4 J2 f6 B
//堆排序的时间复杂度为O（nlgn）
) z* L. x# ~( n! n. y! h* u2 B6 d
temp=A[i];
$ t4 Q d$ O) D: y9 U6 K
A[i]=A[0];
" N/ Y! F: I. C8 M* \8 B
A[0]=temp;
- a/ |1 L8 v8 J2 x! A/ S; x
size--;: C" b5 s7 |- f& T2 `/ ~
MAX_HEAPIFY(A,0,size); Z" T; t$ M2 B( a
& [2 Y8 u" U) N" T% ]" l$ J" s
}: E4 k/ k# x* l: Q) Z, ]8 q' e( A
for(j=0;j<N;j++)
9 A' p# v' H5 I3 Q( j" s5 ?1 N
{7 @0 L# }' ?7 H% G2 j" x" P
printf("%5d",A[j]);
7 F. F5 Y0 u6 _/ _2 \
}
; f( c' {+ \& w( g2 k+ C' f/ w: B6 P
+ H7 t! F- G C
}
% K# u* v% P) t; y
void main(){
* s. `3 R2 e4 \8 H8 ?# D8 l. Z. a
4 p0 q7 b9 s( ~- C1 m6 P
int rand_no=0;3 A% U' L) | E- k
int i=0;# a3 v; k1 K5 f" o7 q
int a[N]; //n表示数组长度% k8 N: Y- \, P0 C+ w
srand((int)time(0)); //设置随机数种子
9 m) m0 I/ ]" U2 [3 r( I
printf("==============================排序前=========================================");: `8 w& l9 |4 Q; X6 z4 E+ X
printf("\n");0 ? n% j/ x* \ X8 g+ w1 z8 X0 ]
for(rand_no=0;rand_no<N;rand_no++)6 _& a' w; m2 _
{ ?/ C% i a5 ^
: r5 Y7 J' {5 V5 P
a[rand_no]=random(100);
- a8 {$ R1 o; z6 s: g: ]
printf("%5d",a[rand_no]);9 ]0 D y' a2 w' w
% [, m0 Z3 r. {& R: v
}9 H" i1 ]6 g; Q- T9 _
printf("\n");( m9 d9 F7 | K" V& ^; B' B
printf("==============================排序后=========================================\n");4 _0 w: l! `) ~$ e6 a% z& O
HEAP_SORT(a);
G! s! r+ w3 [7 M& _
printf("\n"); ( F) Z9 R+ V% ?. z6 Z& ^
! j0 d; r: X+ o W6 y
}
5 x6 F' E( ]8 A- g

复制代码