堆排序(Heap Sort)是指利用堆这种数据结构所设计的一种排序算法。因此，学习堆排序之前，有必要了解堆！若读者不熟悉堆，建议先了解堆(建议可以通过二叉堆，左倾堆，斜堆，二项堆或斐波那契堆等文章进行了解)，然后再来学习本章。
我们知道，堆分为"最大堆"和"最小堆"。最大堆通常被用来进行"升序"排序，而最小堆通常被用来进行"降序"排序。鉴于最大堆和最小堆是对称关系，理解其中一种即可。本文将对最大堆实现的升序排序进行详细说明。
最大堆进行升序排序的基本思想：① 初始化堆：将数列a[1...n]构造成最大堆。② 交换数据：将a[1]和a[n]交换，使a[n]是a[1...n]中的最大值；然后将a[1...n-1]重新调整为最大堆。 接着，将a[1]和a[n-1]交换，使a[n-1]是a[1...n-1]中的最大值；然后将a[1...n-2]重新调整为最大值。 依次类推，直到整个数列都是有序的。
下面，通过图文来解析堆排序的实现过程。注意实现中用到了"数组实现的二叉堆的性质"。在第一个元素的索引为 0 的情形中：性质一：索引为i的左孩子的索引是 (2*i+1);性质二：索引为i的左孩子的索引是 (2*i+2);性质三：索引为i的父结点的索引是 floor((i-1)/2);
堆排序个人总结：
第一步 构建堆的向下调整算法 一个for循环从n/2开始减减； 第二步 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素 heap_sort_asc(a, n)的作用是：对数组a进行升序排序；其中，a是数组，n是数组长度。操作分为两部分：初始化堆 和 交换数据。=两个for循环maxheap_down(a, start, end)是最大堆的向下调整算法。=一个for循环，几个if-else #include <stdio.h> // 数组长度 #define LENGTH(array) ( (sizeof(array)) / (sizeof(array[0])) ) #define swap(a,b) (a^=b,b^=a,a^=b) /* * (最大)堆的向下调整算法 * * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。 * 其中，N为数组下标索引值，如数组中第1个数对应的N为0。 * * 参数说明： * a -- 待排序的数组 * start -- 被下调节点的起始位置(一般为0，表示从第1个开始) * end -- 截至范围(一般为数组中最后一个元素的索引) */ void maxheap_down(int a[], int start, int end) { int start1 = start ; // start 当前(current)节点的位置 int position = 2*start1 + 1; // 左(left)孩子的位置 int tmp = a[start1]; // 当前(current)节点的大小 for( ;position<=end ; ) { if(position<end&&a[position]<a[position+1]) position++; if(a[position]<=tmp) break; else//交换 { a[start1]=a[position]; //将较大值上移 a[position]=tmp; //同时将tmp下移 } start1=position ; //同时start1变为新的 position=2*position+1; //左孩子也变化 } } /* * 堆排序(从小到大) * * 参数说明： * a -- 待排序的数组 * n -- 数组的长度 */ void heap_sort_asc(int a[], int n) { int i; //第一步 构建堆的向下调整算法 for(i=n/2;i>=0;i--) { maxheap_down(a,i,n-1); // 第一步一直执行完所有的 } //第二步 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素 for(i=n-1;i>0;i--) { swap(a[0],a[i]); // 交换一次，将最大值放在数组最后面的a[i]; maxheap_down(a,0,i-1); // 剔除一个最后面的数组元素重新构建堆 } } void main() { int i; int a[] = {20,30,90,40,70,110,60,10,100,50,80}; int ilen = LENGTH(a); printf("before sort:"); for (i=0; i<ilen; i++) printf("%d ", a[i]); printf("\n"); heap_sort_asc(a, ilen); // 升序排列 //heap_sort_desc(a, ilen); // 降序排列 printf("after sort:"); for (i=0; i<ilen; i++) printf("%d ", a[i]); printf("\n"); }转载于:https://www.cnblogs.com/snowwhite/p/4721676.html
