堆排序的时间复杂度是n*logn，可以说吊打冒泡排序(n^2)。是建立在堆这种数据结构的理解上演化出来的一种排序方式。上篇文章对堆这种数据结构已经有详细的介绍。这篇文章就用堆这种数据结构基础搞定堆排序。
一.堆排序思路
堆排序的思路是：若排降序，将给定数据（数组中）建小堆，因为小堆堆顶数据一定最小，每次互换堆顶元素和最后一个元素，将最后一个元素分隔开，然后从堆顶开始向下调整，继续互换堆顶元素和倒数第二个元素，再将倒数第二个分隔开，再从堆顶向下调整，循环这个过程，直到只剩下一个元素为止。若排升序，则建大堆，后续相同。
二.建堆
堆的存储结构是数组，逻辑结构是完全二叉树。要想实现堆排序，首先需要建堆这里提供两种建堆方法：
一.向下调整建堆
first step，找到尾节点的父亲节点
注：灰色数字为数组中的下标
second step，从这个节点开始向下调整，下标顺序为：3->2->1->0
注：红色的数字为向下调整顺序：1->2->3->4
二.向上调整建堆
向下调整建堆的本质就是依次将数据插入堆
插入顺序为：1->2->3->4->5->6->7->8
每次向上调整，将数据一个一个插入堆。可保证最后是一个堆。
三.排序(这里是降序)
降序需要建小堆，排序的逻辑就是每次交换堆顶元素和堆尾（下标为end）元素，分离堆尾元素。
交换完毕后，将堆顶元素向下调整，重新建堆，堆顶元素又成为剩下数据中的最小数据，再交换堆顶元素和堆尾元素(下标为end)，再分离，循环往复，直到堆里只整下一个元素。
四.代码实现及测试
1. void swap(int* pa, int* pb)//交换函数 2. { 3. int tmp = *pa; 4. *pa = *pb; 5. *pb = tmp; 6. } 7. void AdjustDown(int* a, int size, int parent)//建小堆的向下调整 8. { 9. int child = parent * 2 + 1;//左孩子 10. while (child<size) 11. { 12. if (child+1<size&&a[child] > a[child + 1])//找到较小的孩子 13. child++; 14. 15. if (a[parent] >a[child]) 16. { 17. swap(&a[parent], &a[child]); 18. parent = child; 19. child = parent * 2 + 1; 20. } 21. else 22. break; 23. } 24. } 25. int main() 26. { 27. int a[7] = {2,4,5,7,6,8,9};//想要排降序 28. //建小堆 29. int end = 6;//堆尾下标 30. int parent = (end - 1) / 2;//堆尾节点的父亲节点下标 31. while (parent >= 0) 32. { 33. AdjustDown(a, 7, parent);//这里用向下调整建堆 34. parent--; 35. } 36. //排序 37. while (end > 0)//直到堆里只剩下最后一个数据 38. { 39. swap(&a[0], &a[end]); 40. AdjustDown(a, end, 0); 41. end--; 42. } 43. //测试 44. for (int i = 0; i < 7; i++) 45. { 46. printf("%d ", a[i]); 47. } 48. return 0; 49. }
代码测试结果
