堆结构.png

堆排序原理

堆排序的时间复杂度为O(nlogn)

算法原理（以最大堆为例）

o 先将初始数据R[1..n]建成一个最大堆，此堆为初始的无序区 o 再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key

o 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。

o 重复2、3步骤，直到无序区只有一个元素为止。

? c++代码实现

?

1. /**

2. * 将数组arr构建大根堆 3. * @param arr 待调整的数组

4. * @param i 待调整的数组元素的下标 5. * @param len 数组的长度

6. */

7. void heap_adjust(int arr[], int i, int len) 8. {

9. int child; 10. int temp; 11.

12. for (; 2 * i + 1 < len; i = child) 13. {

14. child = 2 * i + 1; // 子结点的位置 = 2 * 父结点的位置 + 1

15. // 得到子结点中键值较大的结点

16. if (child < len - 1 && arr[child + 1] > arr[child])

17. child ++;

18. // 如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点

19. if (arr[i] < arr[child]) 20. {

21. temp = arr[i];

22. arr[i] = arr[child]; 23. arr[child] = temp; 24. } 25. else

26. break; 27. } 28. } 29. 30. /**

31. * 堆排序算法

32. */

33. void heap_sort(int arr[], int len) 34. {

35. int i;

36. // 调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素

37. for (int i = len / 2 - 1; i >= 0; i--) 38. {

39. heap_adjust(arr, i, len); 40. } 41.

42. for (i = len - 1; i > 0; i--) 43. {

44. // 将第1个元素与当前最后一个元素交换，保证当前的最后一个位置的元素都是现在的这个序列中最大的 45. int temp = arr[0]; 46. arr[0] = arr[i]; 47. arr[i] = temp;

48. // 不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值

49. heap_adjust(arr, 0, i); 50. } 51. } 【编辑推荐】

1. 移动开发者服务联盟第二期线下公开课总结：高效，高效，还是高效！ 2. Java习惯用法总结 3. 3年代码总结分享

4. 使用Playground学习数值算法 5. Android 6.0 中的新技术总结