堆排序学习笔记

一.基础准备

        这个算法研究了两天，整整两天啊，中间水了一道线段树，好在皇天不负有心人，嘿嘿。

        1991年计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd）和威廉姆斯(J．Williams）在1964年共同发明了著名的堆排序算法（Heap Sort )。堆排序是高效的排序方法。没有最坏情况（即与平均情况一样），空间占用又小，综合效率比快速排序还好。

        数据结构中的堆和操作系统中的堆、堆栈（栈）是没有关系的，不要有误解。

        说道堆排序就不得不先说堆，树中任一非叶结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字，分别对应大顶堆和小顶堆。堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得在当前无序区中选取最大（或最小）关键字的记录变得简单。

        堆排序（HeapSort）是一树形选择排序。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系（参见二叉树的顺序存储结构），在当前无序区中选择关键字最大（或最小）的记录。堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为O(1），它是不稳定的排序方法。

        注意：①堆中任一子树亦是堆。②以上讨论的堆实际上是二叉堆（Binary

Heap），类似地可定义k叉堆。

        题外话：满二叉树肯定是完全二叉树，完全二叉树不一定是满二叉树；在C和汇编里，位移运算比乘除要快得多。位移运算比加减更快，可能只占一个CPU时钟，乘除要占20多个以上，差了一个数量级。效率而言，那是差不起的。

二.算法理解

三.算法实现

1: //小顶堆      

2: public class W {      

3:      

4:   public static void main(String[] args) {      

5:     //第一个元素不用      

6:     int a[] = {65535,49, 38, 65, 97, 76, 13, 27, 49};      

7:     System.out.print("排序前序列为：");      

8:     for(int i:a) {      

9:       System.out.print(i+" ");      

10:     }      

11:     System.out.println();      

12:     mySort(a,a.length-1);      

13:     System.out.print("排序后序列为：");      

14:     for(int i:a) {      

15:       System.out.print(i+" ");      

16:     }      

17:     System.out.println();      

18:   }      

19:      

20:   private static void mySort(int[] a,int len) {      

21:     //构建小顶堆成功      

22:     for(int i=len/2; i>=1; i--) {      

23:       adjust(a,i,len);      

24: //      System.out.print(a[i]+" "+i+":");      

25: //      for(int j:a) {      

26: //        System.out.print(j+" ");      

27: //      }      

28: //      System.out.println();      

29:     }      

30:     //注意共len-1次循环      

31:     for(int i=1; i<len; i++) {      

32:       /*      

33:        * 注意下边这两句第二个参数都是1      

34:        * 这个for循环里只需要调整一个节点就是根节点，而adjust初初始设计为      

35:        * 从最后开始，不过此时也行了，因为adjust虽然是从最后开始不过      

36:        * 还需要扩展到根节点，很巧妙      

37:        */      

38:       mySwap(a, 1, len-i+1);      

39:       adjust(a, 1,len-i);      

40:     }      

41:   }      

42:      

43:   public static void adjust(int[] a, int i, int len) {      

44:     /*      

45:      * 原来犯了一个错误，更新上一个节点时没有更新子节点即没有采用循环结构      

46:      */      

47:     int temp = a[i];      

48:     int j = i<<1;      

49:     /*      

50:      * 为什么是循环？      

51:      * 因为从最后一个非叶子节点开始的，上面的节点更新后可能使下方      

52:      * 已经调整过的节点不再满足堆的性质，需要继续调整      

53:      */      

54:     while (j<=len) {      

55:       if (j<len && a[j]>a[j+1]) {      

56:         j++;      

57:       }      

58:       if (temp<=a[j]) {      

59:         break;      

60:       }      

61:       a[j>>1] = a[j];      

62:       //往下扩展子节点      

63:       j <<= 1;      

64:     }      

65:     a[j>>1] = temp;      

66:   }      

67:      

68:   private static void mySwap(int[] a, int i, int j) {      

69:     int temp = a[i];      

70:     a[i] = a[j];      

71:     a[j] = temp;      

72:   }      

73: }      

74:      

​