Menu

堆排序–思路代码

2018年4月27日 - 算法,数据结构

堆排序的步骤:

1.首先先将数组转换成二叉树

2.然后找出二叉树的最小堆(最大堆)

小顶堆:父元素比左右子元素都小

 

3.最小堆的概念:每个父节点比左右的子节点都小

调整为小顶堆之后,让堆顶元素与末尾元素进行交换,然后继续调整,直到序列有序

排序是对简单选择排序的改进

简单选择排序是从n个记录中找出一个最小的记录,需要比较n-1次。但是这样的操作并没有把每一趟的比较结果保存下来,在后一趟的比较中,有许多比较在前一趟已经做过了,但由于前一趟排序时未保存这些比较结果,所以后一趟排序时又重复执行了这些比较操作,因而记录的比较次数较多。

堆是具有下列性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。

[算法思想]

将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根节点。将它移走(其实就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素中的次最大值。如此反复执行,就能得到一个有序序列了。

问题:

1. 如何由一个无序序列构建成一个堆?

2. 如何在输出堆顶元素后,调整剩余元素成为一个新的堆?

[java实现]

  1. public class HeapSort {
  2. public static void main(String[] args) {
  3. int[] arr = { 50, 10, 90, 30, 70, 40, 80, 60, 20 };
  4. System.out.println(“排序之前:”);
  5. for (int i = 0; i < arr.length; i++) {
  6. System.out.print(arr[i] + ” “);
  7. }
  8. // 堆排序
  9. heapSort(arr);
  10. System.out.println();
  11. System.out.println(“排序之后:”);
  12. for (int i = 0; i < arr.length; i++) {
  13. System.out.print(arr[i] + ” “);
  14. }
  15. }
  16. /**
  17. * 堆排序
  18. */
  19. private static void heapSort(int[] arr) {
  20. // 将待排序的序列构建成一个大顶堆
  21. for (int i = arr.length / 2; i >= 0; i–){
  22. heapAdjust(arr, i, arr.length);
  23. }
  24. // 逐步将每个最大值的根节点与末尾元素交换,并且再调整二叉树,使其成为大顶堆
  25. for (int i = arr.length – 1; i > 0; i–) {
  26. swap(arr, 0, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换
  27. heapAdjust(arr, 0, i); // 交换之后,需要重新检查堆是否符合大顶堆,不符合则要调整
  28. }
  29. }
  30. /**
  31. * 构建堆的过程
  32. * @param arr 需要排序的数组
  33. * @param i 需要构建堆的根节点的序号
  34. * @param n 数组的长度
  35. */
  36. private static void heapAdjust(int[] arr, int i, int n) {
  37. int child;
  38. int father;
  39. for (father = arr[i]; leftChild(i) < n; i = child) {
  40. child = leftChild(i);
  41. // 如果左子树小于右子树,则需要比较右子树和父节点
  42. if (child != n – 1 && arr[child] < arr[child + 1]) {
  43. child++; // 序号增1,指向右子树
  44. }
  45. // 如果父节点小于孩子结点,则需要交换
  46. if (father < arr[child]) {
  47. arr[i] = arr[child];
  48. } else {
  49. break; // 大顶堆结构未被破坏,不需要调整
  50. }
  51. }
  52. arr[i] = father;
  53. }
  54. // 获取到左孩子结点
  55. private static int leftChild(int i) {
  56. return 2 * i + 1;
  57. }
  58. // 交换元素位置
  59. private static void swap(int[] arr, int index1, int index2) {
  60. int tmp = arr[index1];
  61. arr[index1] = arr[index2];
  62. arr[index2] = tmp;
  63. }
  64. }
1.


2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

 
[算法总结]

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

堆排序对原始记录的排序状态并不敏感,其在性能上要远远好过于冒泡、简单选择、直接插入排序。

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

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

%d 博主赞过: