堆排序:
其基本思想是将待排序的数组构造成一个大顶堆,从而获得数组最大的元素,即当前的根节点。将其移走之后,再把剩余的n-1个数组元素重新构造成一个大顶堆。反复执行,最后得到一个有序序列。
堆排序属于选择排序。

堆排序的过程:
- ① 循环处理元素构造大顶堆
- ② 获取堆顶元素并和最后一个叶节点交换位置
- ③ 重新构建大顶堆,元素个数减一(除去最后一个叶节点,即选出的最大值)。
- ④ 循环第2、3个步骤。
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 46 47 48 49 50 51
| #include <stdio.h>
#define MAXSIZE 100
typedef struct { int r[MAXSIZE+1]; int length; }SortList;
void HeapSort(SortList *L) { int i; for(i=L->length/2;i>0;i--) HeapAdjust(L,i,L->length);
for(i=L->length;i>1;i--) { int temp=L->r[1]; L->r[1]=L->r[i]; L->r[i]=temp; HeapAdjust(L,1,i-1); } }
void HeapAdjust(SortList *L,int s,int m) { int temp,j; temp=L->r[s]; for(j=2*s;j<=m;j*=2) { if(j<m && L->r[j]<L->r[j+1]) ++j; if(temp>=L->r[j]) break; L->r[s]=L->r[j]; s=j; } L->r[s]=temp; }
|
堆排序算法复杂度分析:
在初始化构建大顶堆时,每个非终端结点最多比较两次,所有,这个构建的过程时间复杂度为O(n)。
排序过程中,第i次取堆顶记录重建大顶堆的时间复杂度为O(logi),并且需要取n-1次堆顶记录,所有重建堆的时间复杂度为O(nlogn)。总体上来说,堆排序的时间复杂度为:O(nlogn)。
因为初始化构建堆所需比较次数较多,所以堆排序不适合待排序元素较少的情况。