文章目录
堆排序的概述堆排序的核心思想堆排序函数讲解堆排序完整代码
堆排序的概述
堆排序的思想和简单选择排序思想类似，都是通过不断地寻找最大值，实现数组的排序的。堆排序通过不断的将数组构造成大顶堆，实现排序。 这里出现了大顶堆这个名词，大顶堆的意思是有一个完全二叉树，每个节点的值都大于或者等于其左右孩子节点的值，这样的完全二叉树就是大顶堆。
堆排序的核心思想
我们看这样一个数组[90,70,80,60,10,40,50,30,20],首先将其图形化成为一个完全二叉树。 下面的任务就是取构造大顶堆。
构造大顶堆的方法如下：
将大顶堆划分成一个一个的子二叉树，如下如框线中划分的所示。从下往上，以此将各子二叉树进行调整，注意二叉树的调整是要往下传递的。例如3号子树调整时，有可能还要继续调整1号子树，4号子树调整时，有可能要调整3号子树或者4号子树。 4个子树调整顺序如下： 1号子树：只调整1号子树 2号子树：只调整2号子树 3号子树：调整3号子树+1号子树 4号子树：调整4号子树+3号子树+1号子树 或者 调整4号子树+2号子树
接下来就是堆排序的方法。
构造出一个大顶堆将堆顶的第一个元素和最后一个元素调换位置将剩下的元素继续构造大顶堆，以此类推。
注意：除了第一次构造大顶堆时，需要从下往上所有的子树都进行调整，后面构造大顶堆时，因为只有最上面的子树不符合要求，其他都是符合要求的，所以只需要对最上面的子树进行调整。这一点在代码中也有体现。
堆排序函数讲解
void HeapSort(List *L)
{
int i,j;
for(i=L->length/2;i>0;i--) /* 把L中的r构建成一个大根堆 */
HeapAdjust(L,i,L->length);
print(L);
for(i=L->length;i>1;i--)
{
swap(L,1,i); /* 将堆顶记录和当前未经排序子序列的最后一个记录交换 */
HeapAdjust(L,1,i-1); /* 将L->r[1..i-1]重新调整为大根堆 */
}
}
void HeapAdjust(List *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; /* j为关键字中较大的记录的下标 */
if(temp>=L->r[j])
break; /* rc应插入在位置s上 */
L->r[s]=L->r[j];
s=j;
}
L->r[s]=temp; /* 插入 */
}
堆排序完整代码
#include <stdio.h>
#define MAXSIZE 10000
#define MAX_LENGTH_INSERT_SORT 7 /* 用于快速排序时判断是否选用插入排序阙值 */
#define N 9
typedef struct
{
int a[MAXSIZE+1];
int length;
}
SqList;
void swap(SqList *L,int i,int j);
void print(SqList *L);
void heapSort(SqList *L);
void heapAdjust(SqList *L,int s, int m);
void swap(SqList *L,int i,int j)
{
int temp = L->a[i];
L->a[i] = L->a[j];
L->a[j] = temp;
}
void print(SqList *L)
{
int i = 0;
for(i = 0; i < L->length; i++)
{
printf("%d,",L->a[i]);
}
printf("%d\n",L->a[i]);
}
void heapSort(SqList *L)
{
int i;
for(i = L->length/2; i>0 ; i--)
{
heapAdjust(L,i,L->length);
}
for(i = L->length;i > 1;i--)
{
swap(L,1,i);
heapAdjust(L,1,i-1);
}
}
void heapAdjust(SqList *L,int s, int m)
{
int j,temp;
temp = L->a[s];
for(j = 2*s; j <= m;j *= 2)
{
if(j < m && L->a[j] < L->a[j+1])
j++;
if(temp > L->a[j])
break;
L->a[s] = L->a[j];
s=j;
}
L->a[s] = temp;
}
int main()
{
int d[N]={50,10,90,30,70,40,80,60,20};
SqList test;
int i;
for(i=0;i<N;i++)
test.a[i+1]=d[i];
test.length=N;
print(&test);
heapSort(&test);
print(&test);
}
