概述:堆排,实际上是一种选择排序,只不过采用了堆这种数据结构,利用这种数据结构,使得在每次查找最大元素时,直接选取堆顶元素,从而时间大大缩短,相对简单选择排序算法来说,比较高效。
堆排序算法可描述如下:
1.将待排元素依次存入数组,该数组即为一颗完全二叉树;
2.从最后一个非叶节点开始递减,逐次将每个相应的二叉树调整成最大堆,最后,整个二叉树即为最大堆;
3.交换堆顶元素与堆尾元素,调整新的堆为最大堆,数组分为两部分:堆与已排序列,直至最后一个堆元素。
从上面可以看出,堆排序大致可以分为三个步骤:
1.存入数据(完全二叉树)
2.将前n个元素调整为最大堆
3.交换堆顶和堆尾元素,n=n-1,转2
注:本文元素从数组下标1开始储存,所以parent访问二叉树左右儿子分别为2*parent 和 2*parent+1;
两个核心函数:
- void HeapAdjust(int H[],int start,int end)//堆调整,将start和end之间的元素调整为最大堆
- void HeapSort(int H[],int L,int R)//堆排序
- 1
- 2
核心代码实现:
- void HeapAdjust(int H[],int start,int end)//堆调整,将start和end之间的元素调整为最大堆
- {
- int temp=H[start];
- int parent=start,child;
- while(2*parent<=end)
- {
- child=2*parent;
- if(child!=end&&H[child]<H[child+1])++child;
- if(temp>H[child])break;
- else H[parent]=H[child];
- parent=child;
- }
- H[parent]=temp;
- }
-
- void HeapSort(int H[],int L,int R)
- {
- for(int i=(R-L+1)/2;i>=L;--i)//调整整个二叉树为最大堆
- HeapAdjust(H,i,R);
- for(int i=R;i>=L;--i)
- {
- swap(&H[L],&H[i]);
- HeapAdjust(H,L,i-1);
- }
- }
- 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
测试样例:
- #include <stdio.h>
- #define NA -1
- void swap(int *a,int *b)//该函数用于交换两个变量的值
- {
- int temp=*a;
- *a=*b;
- *b=temp;
- }
- void HeapAdjust(int H[],int start,int end)//堆调整,将start和end之间的元素调整为最大堆
- {
- int temp=H[start];
- int parent=start,child;
- while(2*parent<=end)
- {
- child=2*parent;
- if(child!=end&&H[child]<H[child+1])++child;
- if(temp>H[child])break;
- else H[parent]=H[child];
- parent=child;
- }
- H[parent]=temp;
- }
- void HeapSort(int H[],int L,int R)
- {
- for(int i=(R-L+1)/2;i>=L;--i)//调整整个二叉树为最大堆
- HeapAdjust(H,i,R);
- for(int i=R;i>=L;--i)
- {
- swap(&H[L],&H[i]);
- HeapAdjust(H,L,i-1);
- }
- }
-
- int main(){
- int A[]={NA,1,3,63,5,78,9,12,52,8};//从1开始存入数据
- printf("Previous Arrary:");
- for(int i=1;i<=9;++i)
- printf(" %d",A[i]);
- HeapSort(A,1,9);
- printf("\nSorted Arrary:");
- for(int i=1;i<=9;++i)
- printf(" %d",A[i]);
- printf("\n");
- return 0;
- }
- 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
- 41
- 42
- 43
- 44
- 45
运行结果:
- Previous Arrary: 1 3 63 5 78 9 12 52 8
- Sorted Arrary: 1 3 5 8 9 12 52 63 78
- 请按任意键继续. . .
- 1
- 2
- 3
另:推荐一篇比较详细的文章,读者可以参看堆排序 Heap Sort