堆排序即利用堆的思想来进行排序总共分为两个步骤建堆升序建大堆降序建小堆利用堆删除思想来进行排序建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。voidAdjustUp(HP_Data*a,intchild)//向上调整建堆{intparent(child-1)/2;//计算parent的位置while(child0){if(a[child]a[parent])//当child大于parent时进行交换{Swap(a[child],a[parent]);childparent;parent(child-1)/2;}else{break;//childparent退出}}}voidAdjustDown(HP_Data*a,intn,intparent)//向下调整建堆{HP_Data childparent*21;//计算child的位置默认为左边while(childn){if(child1na[child1]a[child])//为防止计算右边child1的值越界加上条件chikd1n{child;}if(a[child]a[parent])//当child大于parent时进行交换{Swap(a[child],a[parent]);parentchild;childparent*21;}else{break;//childparent退出}}}//堆排序---建大堆voidHeapSort(int*a,intsize){//for (int i 1; i size; i)//向上调整建堆---ON*log_N//{// AdjustUp(a, i);//}for(inti(size-1-1)/2;i0;i--)//向下调整建堆---O(N){AdjustDown(a,size,i);}intendsize-1;while(end0){Swap(a[end],a[0]);AdjustDown(a,end,0);end--;}}intmain(){inta[10]{2,1,5,7,6,8,0,9,4,3};//对数组进行排序HeapSort(a,10);return0;}时间复杂度对比AdjustUp向上调整建堆时间复杂度 O(n log n)AdjustDown向下调整建堆时间复杂度 O(n)用 AdjustDown 建堆每个节点最多向下调整 O(log n) 层但由于底层节点多、调整距离短总操作次数远低于 n log n。直观理解堆的结构特点是上层少、下层多。AdjustDown 从上往下高层的长距离调整只发生在少量节点上而 AdjustUp 从下往上大量底层节点都可能经历较长的调整路径总开销更大。