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

#include<stdio.h>! h5 T5 S9 ~: \3 A5 P5 u/ Q
#include<stdlib.h>! k+ ~' h. R+ N8 m5 F; _6 ~8 Y; [! f6 }
#include<time.h>! m0 X' a. |/ [! f
#define random(i) (rand()%i)
3 X/ F. P5 E2 s
#define N 15
* t/ O0 n9 o' H
: {$ I* w6 d2 }, ?
//维护堆的性质，这里是用的最大堆% J7 z W" R1 h! w7 k5 R
//且为二叉堆
: D: E* w. A& N9 J5 {* T
void MAX_HEAPIFY(int A[],int i,int heapSize){
6 ~. o1 Y( q0 q; C0 S& `" }+ m9 v
int l;//表示节点i的左孩子
" w5 f j7 N" ~: y+ M( R4 s
int r;//表示节点i的右孩子
. H9 E4 D, |* b* C/ w
int largest;//表示最大元素，也就是根.3 k# R; i4 W$ t
int temp;//临时变量，用于交换9 l$ E0 e0 Q+ L* o7 M
int k;
; b* ~0 B* c# |; C* i1 w$ X b
l=2*i+1;
/ O" e+ p- E& d
r=2*i+2;
( F6 a# `: F, I: `
if((l<heapSize)&&(A[l]>A[i])) //如果左孩子大，那么记下下标" X/ |$ A) U" t* M
{6 o N+ |# E1 G+ ~# _* }
largest=l;
% x5 z) t( ?; ~; G
}
/ m3 [4 F# b t5 U
else1 }6 b9 f0 e" g0 ]' i
{ S8 }- y7 b' p: B% A5 s' a
largest=i;% ]" g# p* J* ]% p r& u
2 t$ i2 j7 b" j
}
+ f* j1 s# w. N; C
if ((r<heapSize)&&(A[r]>A[largest]))9 g3 u3 B1 E5 j1 b" `
{ U* J, B# }1 p4 X# n
largest=r;7 k7 @6 S' H* S' A; @
}
1 N$ A) J& I& k% s" k& ` o8 t6 z
if (largest!=i)
9 Z4 ?. K1 e) ~# T
{
8 Z' z8 G2 Z3 E8 e
temp=A[i];* C X% L: |! x
A[i]=A[largest];
' d: }5 _$ o( ~. F) j, I2 {
A[largest]=temp;/ o# p3 T4 u" k3 n3 ^% V
//递归调用: S. Y0 U2 h! ^& V
MAX_HEAPIFY(A,largest,heapSize);
7 c3 U$ x' ^, P) n# K: x) Q$ t
}( d; ]8 _( B: w. R% S- {1 D
/ J2 s* y; Z+ p" ?" q" ^
}; I; f; `- }$ F: n
0 r$ X% K5 S) F: [) E4 A; P
//建堆9 d9 z- a' c6 x* d- ]$ s3 w& f& z" W( g& s
void BUILD_HEAP(int A[]){
4 N d1 U9 c& P; K9 V
int i;% ^6 n8 S# T3 V0 Q) x4 @4 E
for (i=N/2-1;i>=0;i--)
0 R1 X! t7 t+ M: C I! Z
{: ^& L4 f% z9 w# Y6 P
MAX_HEAPIFY(A,i,N);
. x: ~) L# H% y2 L) B6 u4 s
}
" _ f& u$ n/ ?; R' n
: Y4 O! s. H; e5 q+ X( s
}! i- B3 X3 o% M0 J5 r
3 ? r8 U- l1 }3 u* G
//堆排序' D8 M2 F( z. k
void HEAP_SORT(int A[]){
5 U/ m$ {$ G4 P0 P* v
int i;- A6 f4 p5 @$ h$ E
int j=0;5 m) w3 I O: {9 p6 \
int temp; //交换时用的临时变量% t2 w3 p$ ]( L6 p* W8 Z
int size=N; //size代表元素个数
, G) T q# v a5 {) L
//先建堆! R; O: H% i" G5 z0 q& n
BUILD_HEAP(A);
% q2 v& \, w" |9 `
for(i=N-1;i>0;i--)
( i7 H1 y/ i" M2 C7 I8 m5 }
{
6 ~8 g& z3 G2 u. s, u
//因为根节点总是最大的数，我们每次把根节点换到相应位置即可实现排序
3 v/ G/ j, v9 m+ I/ [% [3 I$ P; ?
//堆排序的时间复杂度为O（nlgn）$ `0 i2 J7 X. M& B9 L2 _5 e1 F
temp=A[i];
6 G2 O; i, g$ b m; m' w. C
A[i]=A[0];
, j2 S- V0 |7 F _# Q
A[0]=temp;
' t3 o1 {9 A5 _- m$ x0 z
size--;0 }7 F0 r0 `4 h; ^( o" q" _
MAX_HEAPIFY(A,0,size);( f6 i+ R' A5 Y
; b1 m* j$ @0 x% K7 W
}3 s: h+ E X* t$ j$ D1 W+ x e
for(j=0;j<N;j++)
+ R( K6 V3 q4 Q; l/ V
{. p- k9 `" n; p2 L8 x
printf("%5d",A[j]);8 P6 e. K" E9 T# o* m3 `
}
! V% @. v' P h
+ f& M( c0 o6 a& U8 P! ~7 C1 g
}
' N9 ]6 L9 x, v2 g- Z! `( A
void main(){: S1 i9 N0 v9 z% a
" e0 j! W7 J8 c8 g
int rand_no=0;3 T7 ~, N+ f' v, W
int i=0;( o9 f8 _' E% U' B$ Y7 e5 e
int a[N]; //n表示数组长度
' A: Y" ^0 l% b( j' ?
srand((int)time(0)); //设置随机数种子 b2 n1 p0 {3 E/ {) \7 i
printf("==============================排序前========================================="); c& U: C1 C( P+ @0 j
printf("\n");, D% |- ]9 ?' g' y' {
for(rand_no=0;rand_no<N;rand_no++)4 O1 m7 x$ x1 d* u; u& p0 a
{8 Z. d, A6 [1 B
+ j. r( ?! P; U( l4 t
a[rand_no]=random(100);8 B, H! T( S% o) s2 `' K1 P, L
printf("%5d",a[rand_no]);
$ j2 S5 Z: d, M
9 N( X# P6 s% w. w0 ?
}
+ O- d% f D l, V4 U1 I2 `
printf("\n");
, H8 A0 e; E8 J6 i8 F
printf("==============================排序后=========================================\n");
/ V( U( D4 C" B+ w' n
HEAP_SORT(a);+ p3 n) L7 h7 t2 n/ y& v$ |
printf("\n");
; [0 d( b+ ]9 _9 ?# F7 f) }
! J# K/ X9 F1 R& y: j* Y
6 Q8 e6 X8 X' S0 ?
}+ i1 a& U& y7 \0 }, J S ]. o6 @! m

复制代码