七大排序之堆排序七大排序之堆排序

【七大排序之堆排序】
简单选择排序的改进：减少第i趟排序比较的次数。
对排序的关键：建堆和调整堆。
建堆的过程：
第1趟将索引0至n-1处的全部数据建大顶堆，就可以选出这组数据的最大值。将该堆的根节点跟这组数据的最后1个节点交换，就使得这组数据中最大排在了最后；
第2趟将索引0至n-2处的全部数据建大顶堆，就可以选出这组数据的最大值。将该堆的根节点与这组数据的倒数第2个节点交换，就使的这组数据中最大值排在了倒数第2位；
......
索引0至n-k处的全部数据建大顶堆，就可以选出这组数据的最大值。将该堆的根节点与这组数据的倒数第k个节点交换，就使的这组数据中最大值排在了倒数第k位。
其实整个堆排序过程中, 我们只需重复做两件事：
建堆(初始化+调整堆, 时间复杂度为O(n))；
拿堆的根节点和最后一个节点交换(siftdown, 时间复杂度为O(nlog n) )
因而堆排序整体的时间复杂度为O(nlog n)。
伪代码：

//对下标为i的节点来说 parent(i) return i/2; left(i) return 2*i; right(i) return 2*i+1;

void adjust(int *a, int size,int index) { int left = 2*index; int right = 2*index+1; int parent = index/2; int maxIndex = index; if(lefta[maxIndex]) maxIndex=left; if(righta[maxIndex]) maxIndex=right; //maxIndex是3个数中最大数的下标 if(index != maxIndex) { swap(a[index],a[maxIndex]); adjust(a,size,maxIndex); //递归调整其它不满足堆性质的部分 }}void HeapSort(int *a,int size) { for(int i=size/2-1; i>=0; i--) // 对每一个非叶结点进行堆调整(从最后一个非叶结点开始) { adjust(a,size,i); } for(int i = size-1; i>=1; i--) { swap(a[0],a[i]); //将当前最大的放置到数组末尾； adjust(a,i,0); } }