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

#include<stdio.h>/ b$ o$ e- d8 w
#include<stdlib.h>
* v" T$ ^- r, p& \
#include<time.h>
: t- R! c- F9 B. K, l
#define random(i) (rand()%i)
% J6 r' m' [& G: I2 V+ O! r
#define N 15
7 C6 K, \" ?/ V& r+ u
* p3 Z/ v; o' \* G: h& R! R! c
//维护堆的性质，这里是用的最大堆, V! s/ P: [( P" x! @$ X7 N
//且为二叉堆& M# S: P$ ~5 a# K7 A# O6 o
void MAX_HEAPIFY(int A[],int i,int heapSize){; q1 ?" D# r4 M' {" S. n
int l;//表示节点i的左孩子# |0 P0 P* K( e, t# j# y/ B! K# i
int r;//表示节点i的右孩子. z/ O; _. k% K- e3 P& b
int largest;//表示最大元素，也就是根.
int temp;//临时变量，用于交换
( B1 B& d, Q8 }' I
int k;; S/ e* Q; l% N. _3 m
l=2*i+1;0 L+ N0 l/ c8 A6 h s* W1 @3 w
r=2*i+2;
6 l1 }2 B( }7 g
if((l<heapSize)&&(A[l]>A[i])) //如果左孩子大，那么记下下标
2 F5 w/ M% N5 y+ f b8 r
{6 J, y. m% k" ~! m+ M. }7 J' M9 @2 |! Y
largest=l;
' C7 g6 b/ r3 N. l
}* U1 [/ e. C2 A1 ]7 { K* n
else/ x0 y( [" Q7 c Y
{
1 f" V; j& W" f, t
largest=i;
7 S4 W$ _6 z7 M- m# e
6 m5 \" K& t( O& K
}
' ^, X3 d$ W$ F9 h
if ((r<heapSize)&&(A[r]>A[largest]))
; p2 H* t" H+ F( V, r/ v7 R; a
{
+ [+ } f2 Y5 M3 z- x* n' [) X( [
largest=r;
+ V1 A% D0 M7 C* }4 q) X% B# s
} j9 e3 m( U0 F x
if (largest!=i)9 G R9 D, S- q0 w+ t
{
' D1 G. A8 G& P5 [3 m
temp=A[i];
- S& W9 d% w$ n% O; W# }$ L
A[i]=A[largest];, C1 F7 J! B$ j# f
A[largest]=temp;+ T1 W) H7 q# J% l/ @8 y* d
//递归调用
+ f- w Q, x6 M
MAX_HEAPIFY(A,largest,heapSize);& ^6 h/ {) w* P' O+ a( R, U2 Q
}
( n& z8 U4 y# s3 _. n& V
6 m! n# Y; B0 X: W7 i3 [, _
}
, F+ W% W* _% _8 U3 r
5 G r# R0 o; C1 l4 j
//建堆* ]0 k. ^" G6 S( \; k
void BUILD_HEAP(int A[]){% P5 ^% b; E- i( s' Q+ W4 r v
int i;0 o/ s: Q$ m7 D9 j+ R
for (i=N/2-1;i>=0;i--)5 u2 e. p( [/ S# O3 ]9 m3 _
{* y8 r0 [( u% t$ N
MAX_HEAPIFY(A,i,N); Y2 L+ P! r Z; F* s
}
' c6 k% J+ w+ a
& f& q1 P( ?8 r6 i, f7 S
}
+ p% Q" d* u& X
X( Y7 k2 Z, w$ n1 G
//堆排序8 k3 N7 q, ]5 s, M; ?- d
void HEAP_SORT(int A[]){* i2 c1 f+ `4 K2 L
int i;% q* y' U5 }: f. D) S2 T
int j=0;
# a' k6 ~" d6 ^' k0 \5 g Z) C* C
int temp; //交换时用的临时变量
, z% J) n; O1 W# S7 k, c/ F9 ?
int size=N; //size代表元素个数3 x. o& @: [: a5 l
//先建堆
6 J3 `) y8 b* B. m
BUILD_HEAP(A);
. C+ j1 N9 C8 e) P" H M6 K
for(i=N-1;i>0;i--)
. o) I( K+ z! _
{
5 H' @. E1 e* M; y
//因为根节点总是最大的数，我们每次把根节点换到相应位置即可实现排序: G: i+ Y* y2 l8 }
//堆排序的时间复杂度为O（nlgn）
" A5 v2 p" c# y! Q3 C1 `
temp=A[i];
9 W- i! ]$ S" {! {
A[i]=A[0];
4 o3 T* J& w9 b# |6 B7 H* \
A[0]=temp;
. ?0 H% A. l% A/ z7 r
size--;
* ]9 o; h6 Z! p2 U6 h9 X9 h: T8 W: q
MAX_HEAPIFY(A,0,size);
! V3 i3 Z0 K2 S. X$ }6 R8 D C% Z
8 U( L6 |" @9 o6 m' e
}
/ Y+ I9 y8 f) e% q, E* p
for(j=0;j<N;j++)
- h* d5 v$ b1 V% u4 g Q; Z0 [
{! n7 K* n1 o3 W/ W
printf("%5d",A[j]); G% D- q- Q) j/ {! h/ f% q
}
, L% I7 P7 c5 ~' i2 C
$ {; r; u+ D* X! U
}% P' C. Y) f/ a9 r
void main(){8 K1 _, y$ W/ h
0 W- H& ]+ W* s
int rand_no=0;
7 y4 b+ u& `# `: A( t
int i=0;! |8 I; J' `8 T
int a[N]; //n表示数组长度
3 B; L1 h0 T: y
srand((int)time(0)); //设置随机数种子8 \2 g0 U) H2 {& m$ j
printf("==============================排序前=========================================");
; F! N! u/ z+ A+ f/ B$ X) S
printf("\n");* G* R! O5 s3 D& ?# K. b& r/ k
for(rand_no=0;rand_no<N;rand_no++)
`. m: w: k9 n& R r
{
4 I0 d' }+ D3 f. ]
7 Y" t. `0 M. e" R3 e$ K7 y
a[rand_no]=random(100);+ O* o3 ?# `. I1 w0 @' G* @' k- L
printf("%5d",a[rand_no]);
J0 L1 D! z/ R
( S" m1 d& i/ q# G6 X( G$ ?
}$ w6 b5 Z P; U: }& z1 H
printf("\n");
# F% S' {! ^4 }' F6 _
printf("==============================排序后=========================================\n");3 Z+ z0 |+ c$ N; d/ B" E4 [: K
HEAP_SORT(a);* Z# s; O y# U4 m
printf("\n"); g0 {% [0 Z% G6 t7 H
, A2 S; f4 Q7 j: ^+ p: o
0 @" }# i9 A7 t* ?& `& D
}
! v) j5 O2 j! }1 i' X6 b+ o) X

复制代码