目录

简介：

算法描述：

代码实现：

总结：

简介：

堆排序是利用堆这种数据结构所设计的排序算法，是一种近似于完全二叉树。分为大顶堆和小顶堆。时间复杂度为：o(nlog2(n)),不稳定。

算法描述：

知识储备：一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。

堆排序分为堆的插入和堆的删除

以小顶堆为例：

堆的插入：

//  新加入i结点  其父结点为(i - 1) / 2
void MinHeapFixup(int a[], int i)
{int j, temp;temp = a[i];j = (i - 1) / 2;      //父结点while (j >= 0 && i != 0){if (a[j] <= temp)break;a[i] = a[j];     //把较大的子结点往下移动,替换它的子结点i = j;j = (i - 1) / 2;}a[i] = temp;
}

将数组中的每一个数都插入堆中：

void MinHeapSortInsert(int a[],int n)
{for(int i=1;i<n;i++)MinHeapSortUp(a,i);
}

堆的删除：

堆只能删除根节点，在数组中也就是0号元素。在堆排序中，将堆的最后一个节点与根节点交换，然后再从根节点到叶子节点进行一次自上到下的调整，使之满足最小堆的性质，首先找出左右孩子中最小的那个，与根节点比较，若小于最小的那个孩子节点，则不用调整；否则，进行向下调整。堆的删除相当于下沉过程。

void MinHeapSortDown(int a[],int i,int n)
{int temp=a[i];int j=2*i+1;while(j<n){if(j+1<n&&a[j]>a[j+1])j++;if(temp<=a[j])break;a[i]=a[j];i=j;j=2*i+1;}a[i]=temp;
}

堆排序通过堆的建立，再经过删除，每次删除都是将一个最值放到数组中（此时已经不在堆里），直到堆中没有任何数。

小顶堆通过堆排序得到从大到小的数组。

大顶堆得到从小到大的数组。

代码实现：

#include<iostream>
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
using namespace std;
#define range 10000
void MinHeapSortUp(int a[],int i)
{int temp,j;temp=a[i];j=(i-1)/2;while(j>=0&&i!=0){if(a[j]<=temp)break;a[i]=a[j];i=j;j=(i-1)/2;}a[i]=temp;
}
void MinHeapSortDown(int a[],int i,int n)
{int temp=a[i];int j=2*i+1;while(j<n){if(j+1<n&&a[j]>a[j+1])j++;if(temp<=a[j])break;a[i]=a[j];i=j;j=2*i+1;}a[i]=temp;
}
void MinHeapSortInsert(int a[],int n)
{for(int i=1;i<n;i++)MinHeapSortUp(a,i);
}
void MinHeapSortDelete(int a[],int n)
{int temp;for(int i=n-1;i>=0;i--){temp=a[0];a[0]=a[i];a[i]=temp;MinHeapSortDown(a,0,i-1);}
}void MinHeapSort(int a[],int len)
{MinHeapSortInsert(a,len);MinHeapSortDelete(a,len);
}
int main()
{clock_t start,end;start=clock();freopen("out_arr.txt","r",stdin);freopen("out堆排序.txt","w",stdout);int a[range];int len=range;for(int i=0;i<range;i++){scanf("%d",&a[i]);}MinHeapSort(a,len);for(int i=0;i<range;i++){printf("%5d ",a[i]);if((i+1)%50==0)printf("\n");}end=clock();printf("堆排序耗时：%dms\n",(float)(end-start)*1000.0/CLOCKS_PER_SEC); return 0;
}

 测试结果：

总结：

由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N * logN)。故堆排序的时间复杂度为O(N * logN)。是不稳定的排序算法。

小伙伴们，如果还看不懂，在评论区留言，乐意解答