堆排序
堆排序简单的来说就是一种选择排序的优化.
1.堆
堆实际上是一颗完全二叉树,完全二叉树,所有父节点有两个儿子,或者最后一个父节点只有左儿子.并且父节点的关键字大于或等于所有子节点的关键字
完全二叉树:除最后一层外,每一层上的节点数均达到最大值;在最后一层上只缺少右边的若干结点。
堆表面看也就是逻辑结构是一个树型,然而实际上在内存中是以数组的结构线性存储.
堆分为大顶堆和小顶堆.
大顶堆:根节点的关键字最大.
小顶堆:根节点的关键字最小 .
大顶堆如下 (根节点最小~)
2.堆排序思想
要使用堆排序,首先我们要建立以个大顶堆~,如上图所示
建堆过程:
假设有n个节点,从最后一个父节点(标号为5)起,首先比较最后一个父节点(上图中标号为5)的所有子节点的大小得出较大的子节点,然后用较大的子节点和父节点比较,若大于父节点则交换。
接着到倒数第二个父节点(上图编号为4),比较所有子节点的大小得出较大的子节点,然后用较大的子节点和父节点比较,若大于父节点则交换。
....
于此类推,
直到最后一次父节点为根节点时(上图编号为1),此时根节点是所有节点的最大值,得到大顶堆,且每一个父节点的关键字大于所有子节点。
小顶堆则最小值放到根节点。
现在开始排序~
比如我们利用大顶堆建堆能得到所有节点中最大的节点,在根部,然后我们用根节点的元素(最大)与最后一个节点交换,最后一个节点则用来存放此刻堆的最大值,现在我们假设最后一个节点被排除了,这样就出现了一个新的“
堆 ”且节点个数为n-1,这个堆不满足大顶堆的性质,所以再来一次建新堆的过程,这时根结点又一次为最大值(当然前提是我们已经假设先前的最大节点被排除掉了,此时的最大节点为先前次大),用根节点和新堆的最后一个元素交换,最后一个元素用来存放新堆的最大值。
重复此过程。
我们用不断的建立大顶堆(新堆元素每次减
1),来获得每次新堆的最大值,所以能得到排序后的结果~
建立大顶堆排序,排序结果为从小到大
建立小顶堆排序,排序结果为从大到小
3.代码如下
#include<stdio.h> #include<stdlib.h> struct Node { int Capacity; int *array; }; //交换函数 void exchange(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } //建堆函数 void Adjustheap(struct Node *a) { int i; i = a->Capacity / 2; if(a->Capacity %2 == 1) //元素个数为奇数个和偶数个关系到最后一个父节点的儿子个数 { while(i != 0) { if(a->array[2*i] < a->array[2*i+1]) //比较左右节点,我默认为左节点为较大节点 exchange(a->array+2*i, a->array+2*i+1); if(a->array[i] < a->array[2*i]) //左节点和父节点比较,交换结果父节点为最大值 exchange(a->array+i, a->array+2*i); i--; } } else if(a->Capacity %2 == 0) //元素个数为偶数个情况 { if(a->array[2*i] < a->array[i]) //因为最后一个父节点只有左子节点,情况特殊,单独处理 { exchange(a->array+2*i, a->array+i); } i--; while(i != 0) { if(a->array[2*i] < a->array[2*i+1]) exchange(a->array+2*i, a->array+2*i+1); if(a->array[i] < a->array[2*i]) exchange(a->array+i, a->array+2*i); i--; } } exchange(a->array+1, a->array+(a->Capacity)); //根节点编号为1是最大值,与最后一个节点交换 a->Capacity--; //每次新堆的元素个数减1 } int main() { struct Node *a; int i; int j; printf("Capacity:"); scanf("%d",&a->Capacity); j = a->Capacity; a->array = (int *)malloc(sizeof(int) * (a->Capacity+1)); for(i = 1; i <= a->Capacity; i++) { scanf("%d",a->array+i); } while(a->Capacity >= 1) { Adjustheap(a); } for(i = 1; i <= j; i++) { printf("the value is %d\n",a->array[i]); } return 0; }
运行结果如图:
a->array[1] 是每次找到的最大数。
今天看了看代码,当没有右节点我们也可以自己构造一个,根据排序的顺序可以给里面填充一个无穷大或无穷小的数字来解决。