【转】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>' o y4 P% F' j# {2 C* t
#include<stdlib.h>
( ` u$ F- o; z/ z: g
#include<time.h>- d ^$ \ H; H2 D& H2 Q
#define random(i) (rand()%i)
. v# B& ^4 ^: G- O
#define N 15. y# f! a4 s3 X7 }% A+ I
6 k$ K% d- C' H\" h$ n\" x
//维护堆的性质，这里是用的最大堆# r5 m: d0 i# Z% l7 U' r; q. X
//且为二叉堆
3 }\" J+ q( H: }
void MAX_HEAPIFY(int A[],int i,int heapSize){
$ ]% X7 g& {) v* |% z\" D% j
int l;//表示节点i的左孩子/ B6 Z+ z4 ~4 |
int r;//表示节点i的右孩子
- h6 f+ \- Z& p
int largest;//表示最大元素，也就是根.2 |7 ~- s% Y7 x% V
int temp;//临时变量，用于交换* F0 l# X\" @5 b2 S( g
int k;2 i1 w9 Y, K/ D
l=2*i+1;
7 x' s6 \\" _3 j# X4 q; ]; c
r=2*i+2;! J* U3 O5 _- g! |
if((l<heapSize)&&(A[l]>A[i])) //如果左孩子大，那么记下下标/ f+ s% L* Z3 @) U& b
{6 n k$ e& l& S\" I
largest=l;
, g+ V% Y/ x# X* K
}9 @0 U; c# v1 `) b6 U5 O\" e; T; a
else2 t# R0 t7 @6 @5 j) E
{( C- Z) y4 d/ w1 M8 U
largest=i;5 n: C3 k3 b4 Y. X
4 M6 E3 n+ Z: a
}; x8 ]+ E4 X3 V. C% W8 G
if ((r<heapSize)&&(A[r]>A[largest]))
9 s# W9 R4 q, f+ l5 H
{4 M3 }1 o! x6 H9 s
largest=r;
}
% {2 j5 d- ^0 `. C
if (largest!=i)
6 U, H- O9 x9 R6 l
{
% n1 A- E2 p\" C7 V# d+ c9 g
temp=A[i];
& Q6 [8 x+ Q; J# _( k% H% x
A[i]=A[largest];- M+ b1 n8 b\" c4 \ x! G% V
A[largest]=temp;
) h; ^# n4 I5 s0 T# h- `
//递归调用. c3 k\" O3 @ J: }
MAX_HEAPIFY(A,largest,heapSize); }+ q$ @/ q. q, }- ^3 p
}+ t$ v5 V0 Z+ H$ U3 H# W
% R! B$ R: z2 l) b$ {\" U& ?
}
\" l# y, B$ s9 F; M. J# z2 @% v5 q
8 i\" a- |3 m$ \& G
//建堆
2 Y: |+ y* |) Z* @: @
void BUILD_HEAP(int A[]){
\" x+ R' n h/ Y$ N$ `
int i;\" {' D3 ~( S5 m8 t6 d; e7 q& P
for (i=N/2-1;i>=0;i--)
( j s. d C0 f+ {% ?0 @/ x* w
{/ `( s- S8 `, P
MAX_HEAPIFY(A,i,N);
3 Q/ z* D' z5 t+ X- H2 Z
}
3 o: b# w. K3 v2 Y' J+ T
' b4 A9 {- V8 p& p( c4 Y4 ~
}$ Z% T+ L- Y' K6 l# K
2 l4 P9 ]0 P$ }9 j
//堆排序) U3 _( ]4 Z$ S( t+ T
void HEAP_SORT(int A[]){
# ]# w( D& k ?- ]9 A
int i;
+ Z3 S\" {/ z# Q1 j
int j=0;4 D7 H1 K$ w/ T8 D2 Y
int temp; //交换时用的临时变量
/ g3 r- [! |! A* q i, H\" ^9 [
int size=N; //size代表元素个数
3 R- J1 [ s- Y5 W- q
//先建堆
( V. [' ^5 Z/ J3 M5 ?2 w1 L
BUILD_HEAP(A);
7 @6 r4 S8 O. F& n# z' ~
for(i=N-1;i>0;i--)
! v/ p: e& A/ {+ j
{
9 J. D# y4 D+ y2 q% {
//因为根节点总是最大的数，我们每次把根节点换到相应位置即可实现排序4 c/ V0 z4 c& Q5 S# F7 w# h
//堆排序的时间复杂度为O（nlgn）
4 z6 {' ^9 k$ A\" ]5 j$ J' \& g* `
temp=A[i];
1 w; `* K: {% c: G+ ?( m& p6 V9 C
A[i]=A[0];: a* F3 w f: c) _; m8 O\" h/ E( t) k
A[0]=temp;
# Q1 D3 Q' i( E- ], _+ V3 B8 V! v. x
size--;9 a\" v6 J/ Q2 k\" O7 B
MAX_HEAPIFY(A,0,size);/ ^' x: C# P\" x/ I
$ K7 b# R) M\" y; p; _
}
9 A5 H/ d# q8 U# Q
for(j=0;j<N;j++). v6 J% @7 J1 o, f) Z- w
{# b4 G6 T; n% M6 h3 f/ V3 H
printf("%5d",A[j]);
. [' s* R$ S% `7 m6 |$ Z
}+ e! P. K. \; u
% W+ n0 u/ c# E\" x% u
}
3 T' d6 f5 [; x- _% {; q/ O7 n
void main(){
( a8 e. n, ^; z
' ~& ?& x$ S0 \ d
int rand_no=0;
3 x- l5 p5 E: N4 p, ` M* o
int i=0;2 O/ `1 u) a. O: s! U& g& S
int a[N]; //n表示数组长度
8 ?2 S* \9 u( s\" K0 K9 M
srand((int)time(0)); //设置随机数种子
\" n+ }% i) j$ A' C# P0 d. V, I
printf("==============================排序前=========================================");9 y+ ^ {- C6 y' U, O R; ?/ M2 l
printf("\n");' l& J8 ]3 s8 F7 s
for(rand_no=0;rand_no<N;rand_no++)7 Z2 c* B) N \( }' _
{\" K8 \1 _; t; n
1 l, L' t; e$ @$ U0 Q
a[rand_no]=random(100);
2 E$ `7 a. h5 V- d- ?! _0 y* m
printf("%5d",a[rand_no]);
; X4 n! e H* [/ G
' q K `\" Y! h o, S5 _
}
/ D: ?- k$ L& M( X% o2 F
printf("\n");
+ l; C+ x3 m& J
printf("==============================排序后=========================================\n");
9 q0 t; a' ~8 f7 }; q\" A( y4 {
HEAP_SORT(a);8 `/ F# G% I- {7 ^( a* k\" f
printf("\n");
& ]# b. B, }; Z Q& q- q
! s z! G3 s, y8 G
0 H0 c% _# u! Q- ^
}! M' J' C' A% e( l