【转】c语言版堆排序

[复制链接]

字体大小: 正常放大

wangzheng3056

937 主题	117 听众	3万积分

升级 0%

TA的每日心情

	衰 2020-10-25 11:55

签到天数: 264 天

[LV.8]以坛为家I

自我介绍: 内蒙古大学计算机学院

群组: 2013年数学建模国赛备

电梯直达

发表于 2013-7-31 12:04 |只看该作者 |正序浏览

|招呼Ta 关注Ta

#include<stdio.h>\" o# i4 {9 q5 I; U$ g
#include<stdlib.h>2 t+ W) X\" I1 ]3 k
#include<time.h>! o0 W& ]9 z( I3 H& i0 Y3 y/ m
#define random(i) (rand()%i)
2 ~1 N$ r: q- w
#define N 15- k3 u4 ]8 d6 L+ ~* W5 r; B
' g& m# c/ a5 J0 p
//维护堆的性质，这里是用的最大堆
) m2 _5 v, J7 G9 S% D
//且为二叉堆9 C( l ]9 ~# O
void MAX_HEAPIFY(int A[],int i,int heapSize){, t, P3 ]# |4 D4 W\" D
int l;//表示节点i的左孩子; y* M+ }3 S E. [3 s( z' T* S
int r;//表示节点i的右孩子
6 x+ P# L4 i, V% y6 X2 [# ^. W
int largest;//表示最大元素，也就是根.1 X0 Z( f# a. w3 j. d
int temp;//临时变量，用于交换- p\" C% P2 G\" P
int k;. f3 z V; T7 B4 ]/ R. p
l=2*i+1;4 ]* d4 L/ i# y4 C8 i1 c6 @9 Y
r=2*i+2;; l1 E. j! k) w l$ c
if((l<heapSize)&&(A[l]>A[i])) //如果左孩子大，那么记下下标3 G5 Z. M! V. L5 V7 m2 g: x5 t\" H
{ n* }9 `7 Y, A) z( I! R
largest=l;6 v, a/ Y0 Z8 p) J4 {' _$ q5 `
}3 a5 e: |7 O- i- N5 F& i- \
else
, v5 t0 b( d+ M9 U8 v
{% Q1 v# f8 p' l
largest=i;/ [4 Y7 X$ _* D# X% m
3 h9 }% w' K. T( V% E4 _4 ]
}% I* s; ~) [0 X) Y# H7 T
if ((r<heapSize)&&(A[r]>A[largest]))
( \! G2 q' }: U8 W
{
7 i! g) j) r' Z7 x* P7 \, s* e
largest=r;# c' u3 m8 @% H. c. h
}
$ Q\" }8 ~, }1 U& e
if (largest!=i)
# [+ q+ S\" n1 P+ \; u
{
& {: z; u+ c5 y\" k' \( P' ?: O
temp=A[i];* Y7 r+ p- k9 H. G/ P/ ?) y' y
A[i]=A[largest];$ y- }! q, N, \* N3 K9 W8 y- z
A[largest]=temp;
5 L- @& L' |0 d0 h1 v5 {* H
//递归调用5 a+ _ V4 }! H0 M
MAX_HEAPIFY(A,largest,heapSize);
/ x) K' n% t+ E# N1 r
}& j+ ]3 e. M+ {0 z
9 _0 Z) J7 L8 F$ l. l( i& e
}5 W; t% A( Y! o* p3 m5 I
: C) g( y7 i6 [ H5 K
//建堆
- i; _( o\" S, h$ [\" s3 {& S
void BUILD_HEAP(int A[]){
# u4 |! _& }& D9 k
int i;
Z7 o5 p8 Q) g$ G
for (i=N/2-1;i>=0;i--)
+ W- X\" f& t( s: h* C$ S( S: [
{/ |4 a. e( h* V/ S( G! d\" j
MAX_HEAPIFY(A,i,N);
1 ~8 q% ]5 @, k3 Z0 r) V0 L; ]
}
) H* ]# ~: P3 F: |) b' T
% u* H7 A5 K r% M T% U2 V5 D7 |
}
* l8 N0 |, B# x; l M& W+ i |
1 u- h1 n2 E) X\" O- J' z
//堆排序
* J1 \) |) e7 l4 k4 N# n
void HEAP_SORT(int A[]){
5 P7 U6 i$ t- B8 ^5 x\" B1 w
int i;3 y! A. C+ ~; }3 _8 g V4 A
int j=0;6 z% r9 w6 K6 l6 X0 U2 C+ S O+ o! C4 H
int temp; //交换时用的临时变量
9 k( Z _: p; y\" j, |0 b: O$ {
int size=N; //size代表元素个数
# A- K5 o+ K, V$ k3 }+ b
//先建堆. F0 g. M+ \- l) ` N* M0 m; P/ ?% \
BUILD_HEAP(A);9 I; K8 p' Q! e+ b
for(i=N-1;i>0;i--)
' [\" c0 P7 Y+ h# i$ u$ G4 P
{
/ x2 k+ L% P! S7 a
//因为根节点总是最大的数，我们每次把根节点换到相应位置即可实现排序
' R P! b% ~, O! i; A* q+ S
//堆排序的时间复杂度为O（nlgn）
8 S# z$ E& N1 b( a
temp=A[i];
3 l- m+ v' W3 X) g: a7 T' _
A[i]=A[0];% L\" {3 e\" O3 J* @5 Y/ J
A[0]=temp;3 \8 H- M% F( P
size--;7 ]/ Z- K5 A3 H5 |# p; D' ^
MAX_HEAPIFY(A,0,size);
( Q( U0 v5 y\" F0 Y\" [' C
+ R( J, ~) l/ g4 t' ^8 @\" d% D9 H
}
+ E% ?9 [: X$ x% u
for(j=0;j<N;j++)0 j1 u- D; V1 o) k+ G2 @
{
! I8 `/ L) [: J
printf("%5d",A[j]); m: m# @: n' a! r0 j
}
) {. q& G, N( W
: [( e# F6 o& R, V3 K
}+ Z7 `; F9 A' ^) H, W; ?
void main(){/ Z$ P% U7 v9 O4 ]7 L
* ]% |4 _: W5 k. h: `
int rand_no=0;6 C! q/ n, h' g' ^ c
int i=0;
$ Y; @+ h1 q. M
int a[N]; //n表示数组长度) \1 _6 z- B- u4 i
srand((int)time(0)); //设置随机数种子
/ y2 S8 w3 D8 P; f) _8 M
printf("==============================排序前=========================================");& @; O X1 K\" X) m0 Y; @
printf("\n");
6 p8 t$ V Q\" |- g8 C( b0 J
for(rand_no=0;rand_no<N;rand_no++)9 q( \8 |$ v& D* }# Z6 Y; n
{! j+ w' D& C' z# n
# m% D0 a6 U8 V% x
a[rand_no]=random(100);
8 ^& ?$ K! Y- o% U1 E; d
printf("%5d",a[rand_no]);
$ C, W5 W6 G2 W% S
+ s9 @- F( J\" r J
}
% G Y+ o3 o2 @( h
printf("\n");- U( r* G: A0 X+ m/ k
printf("==============================排序后=========================================\n");7 l h* A; b; ]3 ^8 W' j' Z v
HEAP_SORT(a);
& i2 F* e' X, @2 ^7 A# u
printf("\n"); 7 `) C7 Q4 r, L8 E8 @+ p$ ?. N
; G: p- D2 l+ j0 \6 u
$ ]* l% G9 A% ~; a$ q) p
}
, \$ Y: l2 j6 T( |% E