堆排序实际上是利用堆的性质来进行排序的，要知道堆排序的原理我们首先一定要知道什么是堆。 堆的定义： 堆实际上是一棵完全二叉树。 堆满足两个性质: 1、堆的每一个父节点都大于（或小于）其子节点； 2、堆的每个左子树和右子树也是一个堆。 堆的分类： 堆分为两类： 1、最大堆（大顶堆）：堆的每个父节点都大于其孩子节点； 2、最小堆（小顶堆）：堆的每个父节点都小于其孩子节点； 堆的存储： 一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如下图所示： 堆排序： 由上面的介绍我们可以看出堆的第一个元素要么是最大值（大顶堆），要么是最小值（小顶堆），这样在排序的时候（假设共n个节点），直接将第一个元素和最后一个元素进行交换，然后从第一个元素开始进行向下调整至第n-1个元素。所以，如果需要升序，就建一个大堆，需要降序，就建一个小堆。 堆排序的步骤分为三步: 1、建堆（升序建大堆，降序建小堆）； 2、交换数据； 3、向下调整。 假设我们现在要对数组arr[]={8,5,0,3,7,1,2}进行排序（降序）： 首先要先建小堆： 堆建好了下来就要开始排序了： 现在这个数组就已经是有序的了。 下面给出代码：
void AdjustDown(int arr[], int i, int n){ int j = i * 2 + 1;//子节点 while (j= 0; i--)//((n-1)*2)+1 =n/2-1 { AdjustDown(arr, i, n); }}void HeapSort(int arr[],int len){ int i = 0; MakeHeap(arr, len); for (i = len - 1; i >= 0; i--) { swap(arr[i], arr[0]); AdjustDown(arr, 0, i); }}排序算法（三）堆排序原理与实现（小顶堆）<堆排序的公式>
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至lizi9903@foxmail.com举报，一经查实，本站将立刻删除。