内部排序之堆排序的实现详解
时间：2021-01-30 10:27:28 | 栏目：C代码 | 点击：次
堆排序（Heap Sort）只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。
（1）基本概念
a）堆：设有n个元素的序列：
{k1, k2, ..., kn}
对所有的i=1,2,...,(int)(n/2)，当满足下面关系：
ki≤k2i，ki≤k2i+1
或 ki≥k2i，ki≥k2i+1
这样的序列称为堆。
堆的两种类型：
根结点最小的堆----小根堆。
根结点最大的堆----大根堆。
根结点称为堆顶，即：在一棵完全二叉树中，所有非叶结点的值均小于（或均大于）左、右孩子的值。
b）堆排序：是一种树型选择排序，特点是，在排序过程中，把R[1..n]看成是一个完全二叉树的存储结构，利用完全二叉树双亲结点和孩子结点的内在关系，在当前无序区中选择关键字最大（最小）的记录。
2）堆排序步骤：
1、从k-1层的最右非叶结点开始，使关键字值大（或小）的记录逐步向二叉树的上层移动，最大（或小）关键字记录成为树的根结点，使其成为堆。
2、逐步输出根结点，令r[1]=r[i](i=n,,n-1,...,2)，在将剩余结点调整成堆。直到输出所有结点。我们称这个自堆顶到叶子的调整过程为“筛选”。
（3）要解决的两个问题：
１、如何由一个无序序列建成一个堆；
２、输出一个根结点后，如何将剩余元素调整成一个堆。
将一个无序序列建成一个堆是一个反复“筛选”的过程。若将此序列看成是一个完全二叉树，则最后一个非终端结点是第floor(n/2)个元素，由此“筛选”只需从第floor(n/2)个元素开始。
堆排序中需一个记录大小的辅助空间，每个待排的记录仅占有一个存储空间。堆排序方法当记录较少时，不值得提倡。当n很大时，效率很高。堆排序是不稳定的。
堆排序的算法和筛选的算法如第二节所示。为使排序结果是非递减有序排列，我们在排序算法中先建一个“大顶堆”，即先选得一个关键字为最大的记录并与序列中最后一个记录交换，然后对序列中前n-1个记录进行筛选，重新将它调整为一个“大顶堆”，然后将选得的一个关键字为最大的记录（也就是第一个元素）与当前最后一个记录交换（全局看是第n-1个），如此往复，直到排序结束。由到，筛选应按关键字较大的孩子结点向下进行。
堆排序的算法描述如下：
#include "iostream"
using namespace std;
#define MAXSIZE 20
typedef struct
{
int key;
//其他数据信息
}RedType;
typedef struct
{
RedType r[MAXSIZE+1];
int length;
}Sqlist;
typedef Sqlist HeapType; //堆采用顺序表存储表示
void HeapAdjust(HeapType &H,int s,int m) //已知H.r[s...m]中记录的关键字出H.r[s].key之外均满足堆的定义，本函数调整H.r[s]的关键字，使H.r[s...m]成为一个大顶堆（对其中记录的关键字而言）
{
int j;
RedType rc;
rc=H.r[s];
for(j=2*s;j<=m;j*=2) //沿key较大的孩子结点向下筛选
{
if(j<m && (H.r[j].key<H.r[j+1].key)) //j为key较大的记录的下标
++j;
if(rc.key>=H.r[j].key) //rc应插入在位置s上
break;
H.r[s]=H.r[j]; //将左、右孩子较大的结点与父节点进行交换，建成大顶堆
s=j;
}
H.r[s]=rc; //插入
}
void HeapSort(HeapType &H) //对顺序表H进行堆排序
{
int i;
for(i=H.length/2;i>0;--i) //由一个无序序列建成一个大顶堆，将序列看成是一个完全二叉树，则最后一个非终端节点是第n/2个元素
HeapAdjust(H,i,H.length);
for(i=H.length;i>1;--i)
{
H.r[0]=H.r[1]; //将堆顶记录和当前未经排序的子序列H.r[1...i]中最后一个记录相互交换
H.r[1]=H.r[i];
H.r[i]=H.r[0];
HeapAdjust(H,1,i-1); //将H.r[1...i-1]重新调整为大顶堆
}
}//HeapSort
void InputL(Sqlist &L)
{
int i;
printf("Please input the length:");
scanf("%d",&L.length);
printf("Please input the data needed to sort:\n");
for(i=1;i<=L.length;i++) //从数组的第1个下标开始存储，第0个下标作为一个用于交换的临时变量
scanf("%d",&L.r[i].key);
}
void OutputL(Sqlist &L)
{
int i;
printf("The data after sorting is:\n");
for(i=1;i<=L.length;i++)
printf("%d ",L.r[i].key);
printf("\n");
}
int main(void)
{
Sqlist H;
InputL(H);
HeapSort(H);
OutputL(H);
system("pause");
return 0;
}
不使用上面的结构体的另外一种方法如下：
/*
*堆排序
*/
#include "iostream"
using namespace std;
#define N 10
int array[N];
void man_input(int *array)
{
int i;
for(i=1;i<=N;i++)
{
printf("array[%d]=",i);
scanf("%d",&array[i]);
}
}
void mySwap(int *a,int *b)//交换
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
void heap_adjust(int *heap,int root,int len) //对堆进行调整，使下标从root到len的无序序列成为一个大顶堆
{
int i=2*root;
int t=heap[root];
while(i<=len)
{
if(i<len)
{
if(heap[i]<heap[i+1])
i++;
}
if(t>=heap[i])
break;
heap[i/2]=heap[i];
i=2*i;
}
heap[i/2]=t;
}
void heapSort(int *heap,int len) //堆排序
{
int i;
for(i=len/2;i>0;i--) //由一个无序序列建成一个大顶堆，将序列看成是一个完全二叉树，则最后一个非终端节点是第len/2个元素
{
heap_adjust(heap,i,len);
}
for(i=len;i>=1;i--)
{
mySwap(heap+i,heap+1); //将堆顶记录与最后一个记录相互交换
heap_adjust(heap,1,i-1); //将下标为1~i-1的记录重新调整为大顶堆
}
}
void print_array(int *array,int n)
{
int k;
for(k=1;k<n+1;k++)
{
printf("%d\t",array[k]);
}
}
int main(void)
{
man_input(array);
heapSort(array,N);
printf("\nAfter sorted by the heap_sort algorithm:\n");
print_array(array,N); //打印堆排序结果
system("pause");
return 0;
}
（1）基本概念
a）堆：设有n个元素的序列：
{k1, k2, ..., kn}
对所有的i=1,2,...,(int)(n/2)，当满足下面关系：
ki≤k2i，ki≤k2i+1
或 ki≥k2i，ki≥k2i+1
这样的序列称为堆。
堆的两种类型：
根结点最小的堆----小根堆。
根结点最大的堆----大根堆。
根结点称为堆顶，即：在一棵完全二叉树中，所有非叶结点的值均小于（或均大于）左、右孩子的值。
b）堆排序：是一种树型选择排序，特点是，在排序过程中，把R[1..n]看成是一个完全二叉树的存储结构，利用完全二叉树双亲结点和孩子结点的内在关系，在当前无序区中选择关键字最大（最小）的记录。
2）堆排序步骤：
1、从k-1层的最右非叶结点开始，使关键字值大（或小）的记录逐步向二叉树的上层移动，最大（或小）关键字记录成为树的根结点，使其成为堆。
2、逐步输出根结点，令r[1]=r[i](i=n,,n-1,...,2)，在将剩余结点调整成堆。直到输出所有结点。我们称这个自堆顶到叶子的调整过程为“筛选”。
（3）要解决的两个问题：
１、如何由一个无序序列建成一个堆；
２、输出一个根结点后，如何将剩余元素调整成一个堆。
将一个无序序列建成一个堆是一个反复“筛选”的过程。若将此序列看成是一个完全二叉树，则最后一个非终端结点是第floor(n/2)个元素，由此“筛选”只需从第floor(n/2)个元素开始。
堆排序中需一个记录大小的辅助空间，每个待排的记录仅占有一个存储空间。堆排序方法当记录较少时，不值得提倡。当n很大时，效率很高。堆排序是不稳定的。
堆排序的算法和筛选的算法如第二节所示。为使排序结果是非递减有序排列，我们在排序算法中先建一个“大顶堆”，即先选得一个关键字为最大的记录并与序列中最后一个记录交换，然后对序列中前n-1个记录进行筛选，重新将它调整为一个“大顶堆”，然后将选得的一个关键字为最大的记录（也就是第一个元素）与当前最后一个记录交换（全局看是第n-1个），如此往复，直到排序结束。由到，筛选应按关键字较大的孩子结点向下进行。
堆排序的算法描述如下：
复制代码 代码如下:
#include "iostream"
using namespace std;
#define MAXSIZE 20
typedef struct
{
int key;
//其他数据信息
}RedType;
typedef struct
{
RedType r[MAXSIZE+1];
int length;
}Sqlist;
typedef Sqlist HeapType; //堆采用顺序表存储表示
void HeapAdjust(HeapType &H,int s,int m) //已知H.r[s...m]中记录的关键字出H.r[s].key之外均满足堆的定义，本函数调整H.r[s]的关键字，使H.r[s...m]成为一个大顶堆（对其中记录的关键字而言）
{
int j;
RedType rc;
rc=H.r[s];
for(j=2*s;j<=m;j*=2) //沿key较大的孩子结点向下筛选
{
if(j<m && (H.r[j].key<H.r[j+1].key)) //j为key较大的记录的下标
++j;
if(rc.key>=H.r[j].key) //rc应插入在位置s上
break;
H.r[s]=H.r[j]; //将左、右孩子较大的结点与父节点进行交换，建成大顶堆
s=j;
}
H.r[s]=rc; //插入
}
void HeapSort(HeapType &H) //对顺序表H进行堆排序
{
int i;
for(i=H.length/2;i>0;--i) //由一个无序序列建成一个大顶堆，将序列看成是一个完全二叉树，则最后一个非终端节点是第n/2个元素
HeapAdjust(H,i,H.length);
for(i=H.length;i>1;--i)
{
H.r[0]=H.r[1]; //将堆顶记录和当前未经排序的子序列H.r[1...i]中最后一个记录相互交换
H.r[1]=H.r[i];
H.r[i]=H.r[0];
HeapAdjust(H,1,i-1); //将H.r[1...i-1]重新调整为大顶堆
}
}//HeapSort
void InputL(Sqlist &L)
{
int i;
printf("Please input the length:");
scanf("%d",&L.length);
printf("Please input the data needed to sort:\n");
for(i=1;i<=L.length;i++) //从数组的第1个下标开始存储，第0个下标作为一个用于交换的临时变量
scanf("%d",&L.r[i].key);
}
void OutputL(Sqlist &L)
{
int i;
printf("The data after sorting is:\n");
for(i=1;i<=L.length;i++)
printf("%d ",L.r[i].key);
printf("\n");
}
int main(void)
{
Sqlist H;
InputL(H);
HeapSort(H);
OutputL(H);
system("pause");
return 0;
}
不使用上面的结构体的另外一种方法如下：
复制代码 代码如下:
/*
*堆排序
*/
#include "iostream"
using namespace std;
#define N 10
int array[N];
void man_input(int *array)
{
int i;
for(i=1;i<=N;i++)
{
printf("array[%d]=",i);
scanf("%d",&array[i]);
}
}
void mySwap(int *a,int *b)//交换
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
void heap_adjust(int *heap,int root,int len) //对堆进行调整，使下标从root到len的无序序列成为一个大顶堆
{
int i=2*root;
int t=heap[root];
while(i<=len)
{
if(i<len)
{
if(heap[i]<heap[i+1])
i++;
}
if(t>=heap[i])
break;
heap[i/2]=heap[i];
i=2*i;
}
heap[i/2]=t;
}
void heapSort(int *heap,int len) //堆排序
{
int i;
for(i=len/2;i>0;i--) //由一个无序序列建成一个大顶堆，将序列看成是一个完全二叉树，则最后一个非终端节点是第len/2个元素
{
heap_adjust(heap,i,len);
}
for(i=len;i>=1;i--)
{
mySwap(heap+i,heap+1); //将堆顶记录与最后一个记录相互交换
heap_adjust(heap,1,i-1); //将下标为1~i-1的记录重新调整为大顶堆
}
}
void print_array(int *array,int n)
{
int k;
for(k=1;k<n+1;k++)
{
printf("%d\t",array[k]);
}
}
int main(void)
{
man_input(array);
heapSort(array,N);
printf("\nAfter sorted by the heap_sort algorithm:\n");
print_array(array,N); //打印堆排序结果
system("pause");
return 0;
}