堆排序的时间复杂度是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. }
代码测试结果