堆排序(HeapSort)
站长推荐:NSetup一键部署软件
一键式完成美化安装包制作，自动增量升级，数据统计，数字签名。应对各种复杂场景，脚本模块化拆分，常规复杂的脚本代码，图形化设置。无需专业的研发经验，轻松完成项目部署。(www.nsetup.cn)
本文主要介绍堆排序算法（HeapSort），堆排序像合并排序而不像插入排序，堆排序的运行时间为O(nlgn)；像插入排序而不像合并排序，它是一种原地(in place)排序算法。在任何时候，数组中只有常数个元素存储在输入数组以外，这样，堆排序就把插入排序和合并排序的优点结合起来。
堆排序还引入了另外一种算法设计技术，利用某种数据结构(在此算法中为“堆”)来管理算法执行中的信息。堆数据结构不只在堆排序算法中有用，还可以构成一个有效的优先队列。堆数据结构是一种数组对象，它可以被视为一颗完全二叉树，树种每个结点与数组中存放该结点值的那个元素对应。树的每一层都是填满的，最后一层除外(最后一层从一个结点的左子树开始填)。
一、堆排序算法原理
开始时，堆排序算法先用BuildMaxHeap()函数将n个元素的输入数组array[0...n-1]建造成一个大顶堆。因为数组中最大元素在对应堆树的根A[1]，所以可以通过把它与A[n]互换来达到最终正确的位置。现在如果从堆中“去掉”结点n(通过减小堆大小HeapSize)，可以很容易的将这一数组转换成一个最大堆。原来根的子女仍是最大堆，而新的堆元素可能违背了最大堆性质。这时调用MaxHeapify(array ,temp)函数就可以保持这一性质，由此在A[1...n-1]中构造出最大堆。堆排序算法不断重复这个过程，堆的大小从n-1一直降到2。
二、堆排序算法的实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
#include <iostream> #include <time.h> #include <stdlib.h> #define N 10 using namespace std; //声明建大顶堆函数 void BuildMaxHeap(int * array); //声明堆排序函数 void HeapSort(int * array); //声明调整为大顶堆函数 void MaxHeapify(int * array,int n); //返回堆的数据个数 int HeapSize; int main() { //声明一个待排序数组 int array[N]; //设置随机化种子，避免每次产生相同的随机数 srand(time(0)); for(int i=0 ; i<N ; i++) { array[i] = rand()%101;//数组赋值使用随机函数产生1-100之间的随机数 } cout<<"排序前："<<endl; for(int j=0;j<N;j++) { cout<<array[j]<<" "; } cout<<endl<<"排序后："<<endl; //调用堆排序函数对该数组进行排序 HeapSort(array); for(int k=0;k<N;k++) { cout<<array[k]<<" "; } cout<<endl; return 0; } void HeapSort(int * array) { BuildMaxHeap(array); for(int i=N-1 ; i>=0 ; i--)//数组中下标从0 - N-1 { int temp = array[0]; array[0] = array[i]; array[i] = temp; HeapSize -= 1; MaxHeapify(array,1);//在堆中，堆顶元素下标从1开始 } } void BuildMaxHeap(int * array) { HeapSize = N; for(int i = (N-1)/2 ; i>=1 ; i--)//注意i的取值,堆的高度从1 - (N-1)/2 { MaxHeapify(array,i); } } void MaxHeapify(int * array,int temp) { int largest;//以temp为顶点的子树的堆顶 int l = 2*temp ;//求以temp为顶点的子树左儿子 int r = 2*temp+1;//求以temp为顶点的子树右儿子 if(l <= HeapSize && array[l-1] > array[temp-1])//首先判断左儿子是否存在，即l<=HeapSize { largest = l; }else{ largest = temp; } if(r <= HeapSize && array[r-1] > array[largest-1])//首先判断右儿子是否存在，即r<=HeapSize { largest = r; } if(largest != temp) { int t = array[temp-1]; array[temp-1] = array[largest-1]; array[largest-1] = t; MaxHeapify(array,largest);//调整为大顶堆 } } |
运行结果：
三、堆排序算法分析
堆排序算法集中的插入排序和合并排序的优点，既可以原地排序又有一个较优异的复杂性O(nlgn)，而且所采用的堆数据结构还有一个广泛的应用，作为高效的优先级队列(Priority Queue)。详细应用讲解可以参考《算法导论》原书第二版P80。
另外，须知在实际应用中，快速排序的一个好的实现往往由于堆排序。
学习日记，兼职软件设计，软件修改，毕业设计。
本文出自 学习日记，转载时请注明出处及相应链接。
本文永久链接: https://www.softwareace.cn/?p=170
