堆排序-C语言实现
堆排序
堆排序是利用堆的性质进行的一种选择排序。下面先讨论一下堆。
1.堆
堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:
Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]
即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。
堆分为大顶堆和小顶堆,满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆,满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的,小顶堆的堆顶的关键字是所有关键字中最小的。
2.堆排序的思想
利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单。
其基本思想为(大顶堆):
1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆,此堆为初始的无须区;
2)将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
3)由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。
操作过程如下:
1)初始化堆:将R[1..n]构造为堆;
2)将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换,然后将新的无序区调整为新的堆。
因此对于堆排序,最重要的两个操作就是构造初始堆和调整堆,其实构造初始堆事实上也是调整堆的过程,只不过构造初始堆是对所有的非叶节点都进行调整。
下面举例说明:
给定一个整形数组a[]={16,7,3,20,17,8},对其进行堆排序。
首先根据该数组元素构建一个完全二叉树,得到
然后需要构造初始堆,则从最后一个非叶节点开始调整,调整过程如下:
20和16交换后导致16不满足堆的性质,因此需重新调整
这样就得到了初始堆。
此时3位于堆顶不满堆的性质,则需调整继续调整
#include<stdio.h>
typedef int ElementType;
int arr1[]={,,,,,,,,,,};
#define LeftChild(i) (2 * (i) + 1) void Swap(int* a,int* b)
{
int temp=*a;
*a=*b;
*b=temp;
} void PercDown(int A[], int i, int N)
{
int child;
ElementType Tmp; for (Tmp = A[i]; *i+ < N; i = child){
child = *i+; //注意数组下标是从0开始的,所以左孩子的求发不是2*i
if (child != N - && A[child + ] > A[child])
++child; //找到最大的儿子节点
if (Tmp < A[child])
A[i] = A[child];
else
break;
}
A[i] = Tmp;
} void HeapSort(int A[], int N)
{
int i;
for (i = N / ; i >= ; --i)
PercDown(A, i, N); //构造堆
for(i=N-;i>;--i)
{
Swap(&A[],&A[i]); //将最大元素(根)与数组末尾元素交换,从而删除最大元素,重新构造堆
PercDown(A, , i);
}
} void Print(int A[],int N)
{
int i;
for(i=;i<N;i++)
{
printf(" %d ",A[i]);
}
}
int main()
{
int arr[]={,,,,,,,,,};
Print(arr,);
printf("\n");
HeapSort(arr,);
Print(arr,);
printf("\n");
return ;
}
运行结果:
最新文章
- 【转】jQuery异步上传文件
- Codeforces Round #313 (Div. 2) D. Equivalent Strings
- C数据类型
- java小程序 实例 二分法查找
- SQL笔记-第二章,数据表的创建和管理
- 随堂作业——到底有几个“1”(C++)
- android 开发自建wifi热点的默认ip
- HDU 1150 Machine Schedule (二分图最小点覆盖)
- SCOI2009游戏
- Linux iconv使用
- C++多文件变量
- S全选功能代码
- Spark学习之Spark调优与调试(一)
- Fiddler无法正常抓取谷歌等浏览器的请求_解决方案
- linux中查找(find、locate、which、whereis、grep)命令汇总、帮助命令(man、whatis、apropos、info、help)汇总
- 与http协作的web服务器--代理、网关、隧道
- TCP/IP 笔记 - TCP拥塞控制
- 微信接口开发之高级篇系列【微信JS-SDK】
- Android Service总结05 之IntentService
- intellij idea移动至方法块function()末尾的快捷键