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

#include<stdio.h>
8 K- w) ^& j) c
#include<stdlib.h>7 Q8 A+ n) l7 t
#include<time.h>
" e# c0 ^; j9 c# ?, d6 Q0 {
#define random(i) (rand()%i)
; u( q* V: t- ` J7 H
#define N 15, L0 q# ~7 T$ e7 }* R, e I; [
3 c) U* y9 Q. v
//维护堆的性质，这里是用的最大堆
2 h2 T; L6 h) {! Q4 `! ~0 y
//且为二叉堆
5 b9 A% x8 ^) w4 e
void MAX_HEAPIFY(int A[],int i,int heapSize){
# s$ N# z8 `( K1 s
int l;//表示节点i的左孩子
$ q2 ^8 {3 c. u1 G
int r;//表示节点i的右孩子- Y; B- Y# p, R4 H7 w" x% y( u6 @
int largest;//表示最大元素，也就是根.
3 }4 y. R/ @0 d; }1 c
int temp;//临时变量，用于交换
3 d* t1 C+ `/ A4 S$ R3 @4 P) i1 _
int k;+ }- D7 \" x) q8 Z2 J8 d- q+ ?
l=2*i+1;
4 T" @1 Y& |. F" z/ k
r=2*i+2;( z5 B: C; ]% x d5 j
if((l<heapSize)&&(A[l]>A[i])) //如果左孩子大，那么记下下标
9 Z* [5 A9 u f
{
+ b3 @" N% r$ x
largest=l;; {/ X9 u* u0 B' O+ Q
}6 M) D: z0 V f; n, M
else) a- \! N9 F+ V# [
{, C+ p7 ?6 l2 } P! R: B3 Z8 O
largest=i;, f# W z6 G# c5 W% V3 k9 `, O
, n# N4 y. N. d9 v. s% X- l2 L
}8 {; X) X4 x# w
if ((r<heapSize)&&(A[r]>A[largest]))
4 A9 C6 V! A( m$ Z c$ ?
{
5 R% X j; ]5 ~8 e0 b( J
largest=r;
- T7 y$ U! k) ^" k& C5 `' ^: t
}
9 R r8 y: P4 i4 r9 G
if (largest!=i)
9 G3 t: A6 l" O5 A
{
/ X$ u! _- D- e; v+ z! v
temp=A[i];
2 i/ ^$ J5 D: Y: n6 M
A[i]=A[largest];
& D/ [4 J/ c2 R _) u
A[largest]=temp;
4 j1 S$ y' q1 E. z; B
//递归调用
2 b. i6 y6 ?/ w- l& V
MAX_HEAPIFY(A,largest,heapSize);+ x7 `# V5 I: ^( Z f
}4 R. \5 Q& A0 B2 N
: l, ~/ x$ N$ L( @, R+ H
}
& A0 A3 P+ X+ m9 L
! T) u6 j& @8 L" c4 C
//建堆
L) ~' Z' [% ^8 D/ j, Q
void BUILD_HEAP(int A[]){* y3 R4 ^9 s4 P1 o% m, R3 w
int i;, i$ h" I3 Z ^! H9 ~) w5 O, g3 g+ @
for (i=N/2-1;i>=0;i--)0 g" E5 F& z7 m) A; E6 V l( n1 o
{( ~: Q( X6 }2 j9 T: O' k5 e- O
MAX_HEAPIFY(A,i,N);, W9 i7 j/ [; b: i9 }
}
8 N! h9 q* N% l" E9 _
- V o& g6 c) d5 R/ Z9 R2 }" |
}
7 U5 A) @" m! Q# _2 D" B
9 \9 J7 C! c' k
//堆排序
) w/ K3 y9 |# n
void HEAP_SORT(int A[]){. N( Z- A+ ^. d# P/ x
int i;) _. G8 w5 q8 _" W! d
int j=0;0 L8 S4 t1 N) ~6 e N* L% e% H8 R
int temp; //交换时用的临时变量
9 x# f1 u" ~, `: \1 R4 h6 v
int size=N; //size代表元素个数 F" s5 ^8 S q( |/ T, H
//先建堆7 G" Z7 v5 ]6 n* y6 m) _
BUILD_HEAP(A);
, k7 L- ?8 n; @9 ?" O/ ~; M, @
for(i=N-1;i>0;i--)
" n0 W& Z3 f3 |. l( e/ d/ Z/ G) @
{) L$ M/ N3 z4 [1 i) Q/ b
//因为根节点总是最大的数，我们每次把根节点换到相应位置即可实现排序( g+ [- w: s) e" F6 Y
//堆排序的时间复杂度为O（nlgn）
3 E1 n- D' g6 n# ~7 e
temp=A[i];3 Q9 l. d9 e% a9 n& n: |* x
A[i]=A[0];
; A( U' s4 i# i) a+ h0 {7 U
A[0]=temp;
, m" }: M# s5 M* r6 s, K$ h! c
size--;8 ~% N8 F3 U8 t3 F
MAX_HEAPIFY(A,0,size);# _- C- p8 ?& P
6 I5 Z. V# [/ u1 J! g8 }
}8 b9 c/ [: }1 h; [
for(j=0;j<N;j++)
3 s4 k' y; \; n* U. A5 B
{
9 ~9 L: C& L2 @ H/ e6 @+ Y
printf("%5d",A[j]);/ c/ L2 K6 p: d9 E& a4 i, g( z
}/ j* B9 Z' F, W# w' ^5 F' G, @
# k2 ~) d) } U1 M9 U( m, f( K
}
. ]& Z& W$ S7 @1 T# \
void main(){
1 L6 }4 j* E7 e5 B& m
, w# W9 v% k& Q1 Q+ g! d/ g
int rand_no=0;
1 N7 D# C7 E1 _, T3 y
int i=0;* \2 w, {+ m6 n, Y4 b$ x4 g! `6 r
int a[N]; //n表示数组长度0 D# C4 C0 M. {3 \9 t8 F
srand((int)time(0)); //设置随机数种子
& F, u3 k: L3 T! [9 w4 _
printf("==============================排序前=========================================");
7 ~% B$ P$ f; Z* `
printf("\n");- R3 c1 A9 ?: j# {# ]0 t
for(rand_no=0;rand_no<N;rand_no++)
- ~! l1 l) A: a. ]8 D
{
- q7 l6 [" w8 ]6 o. F* c
A% Q# M& Y& F8 T5 X
a[rand_no]=random(100);$ F; G( B% i* `. k
printf("%5d",a[rand_no]);
( z% I7 N1 f* w: y
: d0 Q* }9 V3 V9 f1 `5 p/ N% [2 r
}
0 s; x) d8 U1 p2 s0 C3 a1 m
printf("\n");
; A/ A0 I4 L8 q
printf("==============================排序后=========================================\n");. G! }/ h# I0 B) v% J) H6 Z+ x# T
HEAP_SORT(a);
! {6 W1 }* F, S3 _ Y
printf("\n");
; Z# ]$ v7 @2 E, H
, x" F9 g/ V$ y! U$ {5 P% Z
- l4 [8 C8 t/ g+ k9 @- E
}1 p" L* N3 Z) C; J

复制代码