C语言堆排序 | Eternal_zttz

C语言堆排序

堆排序:堆排序可以看成优化版的选择排序

堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了
其算法时间复杂度为O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
#define SWAP(a,b) {int t = a;a = b;b = t;}
void adjust(int a[],int i,int n);
void heapSort(int a[],int n);
int main(){
int i,n;
scanf("%d",&n);
int num[n];
for (i =0 ;i<n;i++)
scanf("%d",&num[i]);
heapSort(num,n);
for (i =0;i<n;i++)
printf("%d ",num[i]);
}

void adjust(int a[],int i,int n){
int j,temp;
temp = a[i];
j = 2*i+1;
while(j<n){
if(j+1<n&&a[j]<a[j+1])
j++;
if(temp<a[j]){
a[(j-1)/2] = a[j];
j = 2*j+1;
}
else
break;
}
a[(j-1)/2] = temp;
}
void heapSort(int a[],int n){
int i;
for (i = n/2-1;i>=0;i--)
adjust(a,i,n);
for (i = n-1;i>=1;i--){
SWAP(a[0],a[i]);
adjust(a,0,i);
}
}

程序输入:

1
2
9
1 5 6 8 4 3 2 9 15

程序输出:

1
1 2 3 4 5 6 8 9 15


-------------The End-------------