【转】c语言版堆排序

[复制链接]

字体大小: 正常放大

wangzheng3056

937 主题	117 听众	3万积分

升级 0%

TA的每日心情

	衰 2020-10-25 11:55

签到天数: 264 天

[LV.8]以坛为家I

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

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

电梯直达

1^#

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

|招呼Ta 关注Ta

#include<stdio.h>8 a1 I) P/ h6 h# C! L( x( c
#include<stdlib.h>
% O; I# z! i. H% p0 @ M0 J4 ?' T
#include<time.h>
& u( Y0 T( p# X Q; c
#define random(i) (rand()%i)
. u2 p7 Y) Q- a! g
#define N 15
. G; v% h4 g9 X# W) h& Y
* m+ r* p. R* Z: ^' I) V0 {
//维护堆的性质，这里是用的最大堆& r& Z' Q% W\" a {2 H
//且为二叉堆
2 C1 r. y! h\" X! P/ D& E& n
void MAX_HEAPIFY(int A[],int i,int heapSize){( U1 [; }3 t# t- ]% P0 j# ^
int l;//表示节点i的左孩子# n& ?( A3 u: p+ m3 T# P1 e% t
int r;//表示节点i的右孩子/ Z! ]& }/ d) T [$ [5 e
int largest;//表示最大元素，也就是根.
$ x' V- k4 e* K6 w
int temp;//临时变量，用于交换
# |6 F: s- E5 N
int k;
$ q8 y2 D7 H# P6 P8 ~$ B
l=2*i+1;
# I1 h+ ~( o# I% R6 U& F7 O2 B# X% g
r=2*i+2;& f9 I1 f5 w3 F3 w\" e
if((l<heapSize)&&(A[l]>A[i])) //如果左孩子大，那么记下下标
; T9 i8 P4 x) d
{
% P6 X8 Q: G6 ^5 Q5 u/ V* F8 @. Q
largest=l;4 _. _- L% R2 O5 f, [& g
}
0 T; N$ S9 m\" K+ A/ y* d% S, Z; S
else/ u; m( d- a* {\" k% g' k
{2 O9 E3 [$ Y# n6 D7 L& Y+ |1 T
largest=i;* F6 Z9 \0 u. D1 [
0 n5 H+ @9 ?7 V1 e
}
6 G/ I7 f\" |* b, i! {0 x
if ((r<heapSize)&&(A[r]>A[largest])); e! Q- n1 a( P0 w2 X9 ?0 }
{8 `& k+ \1 }8 n; `\" g# t
largest=r;
( h$ n: E, I0 u\" A4 |' S\" J
}
3 ^2 X: Y0 p! ~& @6 T
if (largest!=i)4 a6 `; W6 j; I y1 X4 ~$ M
{
$ p) ?% s$ P2 D- c7 R
temp=A[i];
r6 H: H# }* y8 k4 A N
A[i]=A[largest];* R( c! ~% Z% u, w% B# F6 N
A[largest]=temp;
; d! `6 \4 y3 G/ c
//递归调用
2 B' w u% d. Z7 x\" Z1 [9 W
MAX_HEAPIFY(A,largest,heapSize);2 N\" G1 a3 t7 a3 d0 B& Y6 _; U/ U
}8 r# \& \1 q6 e! V0 Z( X
$ `' u7 r) l: [1 Z6 Q# N. j
}5 L0 l% |9 d7 W$ l' k3 [
q/ h* {/ x1 \. z5 w( C
//建堆
/ C+ j$ J. D( N: F0 H& k. D8 R: _9 y
void BUILD_HEAP(int A[]){
) l- {4 p, i$ I2 w
int i;8 V* a9 M! s R! b8 r! V
for (i=N/2-1;i>=0;i--): Q- B0 E( {$ X/ P2 @
{
8 H3 y% X. }: `+ T9 n
MAX_HEAPIFY(A,i,N);! _* Y$ O6 F7 g7 {) g8 X9 p9 F# F. m [
}
0 O4 C/ P4 C! l9 u: K( l! h
4 U2 b: z# A4 K+ p2 E
}0 {5 R. O4 F* y3 I/ A _/ E
2 f; k6 ]\" a! A {) p) c9 q
//堆排序3 D7 h( ^: ~5 e\" K
void HEAP_SORT(int A[]){
; C8 S; G0 {, L0 ?2 ?* X
int i;( ~4 s6 z$ U8 V
int j=0;
/ M# T- g$ G' E2 p
int temp; //交换时用的临时变量
; o! _) I+ f, S+ V( n. q
int size=N; //size代表元素个数& p. a/ _0 O- w1 N1 e0 w9 U
//先建堆9 o, b* G) U! |9 o4 Y
BUILD_HEAP(A);7 i# Y# \, C; y0 _\" N! T; |
for(i=N-1;i>0;i--)
% D6 K/ A0 R' Z- X0 I9 A
{8 Q% o+ U: }2 b8 P0 x! e* I
//因为根节点总是最大的数，我们每次把根节点换到相应位置即可实现排序4 P\" V* b( P; _; F2 B
//堆排序的时间复杂度为O（nlgn）
) u, p: ^' {7 W2 G/ V5 J
temp=A[i];
* p7 |0 k2 P: m7 Q\" y- i0 t
A[i]=A[0];) E. P7 s- G, x3 A. v& W
A[0]=temp;. ^' j3 `\" Y$ a! M6 \
size--;
5 X/ R# Y0 c, T& M2 K0 a
MAX_HEAPIFY(A,0,size);
$ H5 V- Y\" Z6 d. `0 |* u
( a, e7 R\" \' `: H% v
}
, T1 E! e8 H2 S
for(j=0;j<N;j++) p. t9 k$ j0 c# M1 Z
{. I/ R, O0 r/ h' [
printf("%5d",A[j]);: Z2 Q/ `3 u9 g( q; g1 \+ K1 M0 n
}
* l9 a8 }+ O' D) A/ {! h
! @. u: ]# m2 ] {& q! ^
}$ d# H8 D' M2 Z. Z
void main(){
% v) Z: C6 t l9 }6 q; o) T
2 o$ G5 f7 l, I T( h2 F
int rand_no=0;
$ N' R2 f/ E) z+ _
int i=0;& z$ H$ h+ D1 p. R' S3 {
int a[N]; //n表示数组长度6 q4 `5 @; h d1 g
srand((int)time(0)); //设置随机数种子
+ @; S1 ]+ M! O, n7 y. b
printf("==============================排序前=========================================");
8 F: x- e1 `. b8 m; A& @: G* K
printf("\n");
* D( W; E; G* r) H* j( r6 s# a
for(rand_no=0;rand_no<N;rand_no++)
. w\" p0 E+ I# e5 s
{5 A2 ^0 z1 m) Q3 O7 M7 Y! o
+ y3 S; S\" F0 C. D7 Q2 S' }0 M2 s8 e- F
a[rand_no]=random(100);( o6 d' H& s7 | j& t6 [
printf("%5d",a[rand_no]);
( o' c, o4 i& _0 b' q
$ p( [; C) [ A
}
& T+ O, k% [ w: s. G9 e# y
printf("\n");! P s\" u6 F: w/ t/ A; e2 R/ f0 f
printf("==============================排序后=========================================\n");1 x9 D: Z) j+ a9 r* |1 L4 |$ o
HEAP_SORT(a);
: |0 {- f: [% o4 b
printf("\n"); r* @' S2 G+ Z
6 a6 e7 L\" x& ^+ h
# I8 J1 N( J, a\" M& j
}+ t* [# D5 d/ B6 C4 r6 X# x1 g