/*
================================================
功能:堆排序
输入:数组名称(也就是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述:
堆排序是一种树形选择排序,是对直接选择排序的有效改进。
堆的定义如下:具有n个元素的序列(h1,h2,...,hn),当且仅当
满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,...,n/2)
时称之为堆。在这里只讨论满足前者条件的堆。
由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项。完全二叉树可以很直观地表示堆的结构。堆顶为根,其它为左子树、右子树。
初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的存储顺序,使之成为一个堆,这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。
从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。
堆排序是不稳定的。算法时间复杂度O(nlog2n)。
*/
/*
功能:渗透建堆
输入:数组名称(也就是数组首地址)、参与建堆元素的个数、从第几个元素开始
*/
void sift(int *x, int n, int s)
{
int t, k, j;
t = *(x+s); /*暂存开始元素*/
k = s; /*开始元素下标*/
j = 2*k + 1; /*右子树元素下标*/
while (j { if (j { j++; } if (t<*(x+j)) /*调整*/ { *(x+k) = *(x+j); k = j; /*调整后,开始元素也随之调整*/ j = 2*k + 1; } else /*没有需要调整了,已经是个堆了,退出循环。*/ { break; } } *(x+k) = t; /*开始元素放到它正确位置*/ } /* 功能:堆排序 输入:数组名称(也就是数组首地址)、数组中元素个数 */ void heap_sort(int *x, int n) { int i, k, t; int *p; for (i=n/2-1; i>=0; i--) { sift(x,n,i); /*初始建堆*/ } for (k=n-1; k>=1; k--) { t = *(x+0); /*堆顶放到最后*/ *(x+0) = *(x+k); *(x+k) = t; sift(x,k,0); /*剩下的数再建堆*/ } } void main() { #define MAX 4 int *p, i, a[MAX]; /*录入测试数据*/ p = a; printf("Input %d number for sorting :/n",MAX); for (i=0; i { scanf("%d",p++); } printf("/n"); /*测试选择排序*/ p = a; select_sort(p,MAX); /**/ /*测试直接插入排序*/ /* p = a; insert_sort(p,MAX); */ /*测试冒泡排序*/ /* p = a; insert_sort(p,MAX); */ /*测试快速排序*/ /* p = a; quick_sort(p,0,MAX-1); */ /*测试堆排序*/ /* p = a; heap_sort(p,MAX); */ for (p=a, i=0; i { printf("%d ",*p++); } printf("/n"); system("pause"); } 编辑特别推荐: 冒泡排序的优化写法
① 凡本网注明稿件来源为"原创"的所有文字、图片和音视频稿件,版权均属本网所有。任何媒体、网站或个人转载、链接转贴或以其他方式复制发表时必须注明"稿件来源:我考网",违者本网将依法追究责任;
② 本网部分稿件来源于网络,任何单位或个人认为我考网发布的内容可能涉嫌侵犯其合法权益,应该及时向我考网书面反馈,并提供身份证明、权属证明及详细侵权情况证明,我考网在收到上述法律文件后,将会尽快移除被控侵权内容。