堆排序算法及其稳定性分析

什么是堆排序？

堆排序是利用数据结构堆而设计的一种排序算法。

堆分为两种，大顶堆和小顶堆。

所谓大顶堆就是每个节点的值都大于或者等于其左右孩子节点的值。

小顶堆则是相反的，每个节点的值都小于或者等于其左右孩子节点的值。

下面是一个大顶堆的示例，其拥有下面的性质:

arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

heapsort1

下面是一个小顶堆的实例，其拥有下面的性质：

arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

heapsort2

大顶堆和小顶堆数据结构是堆排序的基础，下面就看堆排序是如何利用堆来进行排序的。

堆排序的步骤如下：

1.将原始数组转换成一个大顶堆(如果要求升序)或者小顶堆(如果要求降序)。
2.将大顶堆或者小顶堆的首元素与最后一个元素交换
3.剔除尾部元素，将剩下的元素重新构成一个大顶堆或者小顶堆，重复2。

以一个例子来看一下上述过程是怎样的。

原始数组arr = [3,1,4,5,2]，对其进行升序。

步骤1：首先将原数组构建成一个大顶堆。首先从叶子节点开始，将1和5进行对调。

heapsort-demo

步骤2：继续进行调整，将5和3进行对调，此时已经成为了一个大顶堆。

heapsort-demo

步骤3：将堆顶元素5和尾部元素2进行对调。

heapsort-demo

步骤4：重新构建一个大顶堆。将2和4进行对调。

heapsort-demo

步骤5：将堆顶元素4和尾部元素1进行对调。

heapsort-demo

步骤6：重新构建一个大顶堆。将元素1和3进行对调。

heapsort-demo

步骤7：将堆顶元素3和尾部元素2进行对调。

heapsort-demo

步骤8：将堆顶元素2和尾部元素1进行对调。

heapsort-demo

复杂度：

时间复杂度： $O (n l o g n)$

空间复杂度为: $O (1)$ 。没有使用额外的存储空间。

堆排序的代码实现

#include <stdio.h>    
#include <string.h>
#include <ctype.h>      
#include <stdlib.h>   
#include <math.h>  
#include <time.h>

typedef int Status; 


#define MAXSIZE 10000  /* 用于要排序数组个数最大值，可根据需要修改 */
typedef struct
{
	int r[MAXSIZE+1];	/* 用于存储要排序数组，r[0]用作哨兵或临时变量 */
	int length;			/* 用于记录顺序表的长度 */
}SqList;

/* 交换L中数组r的下标为i和j的值 */
void swap(SqList *L,int i,int j) 
{ 
	int temp=L->r[i]; 
	L->r[i]=L->r[j]; 
	L->r[j]=temp; 
}

void print(SqList L)
{
	int i;
	for(i=1;i<L.length;i++)
		printf("%d,",L.r[i]);
	printf("%d",L.r[i]);
	printf("\n");
}


/* 已知L->r[s..m]中记录的关键字除L->r[s]之外均满足堆的定义， */
/* 本函数调整L->r[s]的关键字,使L->r[s..m]成为一个大顶堆 */
void HeapAdjust(SqList *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; /* 插入 */
}

/*  对顺序表L进行堆排序 */
void HeapSort(SqList *L)
{
	int i;
	for(i=L->length/2;i>0;i--) /*  把L中的r构建成一个大根堆 */
		 HeapAdjust(L,i,L->length);

	for(i=L->length;i>1;i--)
	{ 
		 swap(L,1,i); /* 将堆顶记录和当前未经排序子序列的最后一个记录交换 */
		 HeapAdjust(L,1,i-1); /*  将L->r[1..i-1]重新调整为大根堆 */
	}
}

/* **************************************** */


#define N 9
int main()
{
   int i;
   
   /* int d[N]={9,1,5,8,3,7,4,6,2}; */
   int d[N]={50,10,90,30,70,40,80,60,20};
   /* int d[N]={9,8,7,6,5,4,3,2,1}; */

   SqList l0,l1,l2,l3,l4,l5,l6,l7,l8,l9,l10;
   
   for(i=0;i<N;i++)
     l0.r[i+1]=d[i];
   l0.length=N;
   l1=l2=l3=l4=l5=l6=l7=l8=l9=l10=l0;
   printf("排序前:\n");
   print(l0);
	
   printf("堆排序:\n");
   HeapSort(&l6);
   print(l6);

	return 0;
}