堆排序&二叉树排序&希尔排序_二叉排序树和堆排序时间复杂度谁大

堆排序

堆就是一个完全二叉树， 可以用数组来实现；
大根堆：任何一棵子树最大的是子树的头部；

建立大根堆的过程 O(n), 顺序遍历数组，每个元素作为 index, index 只与父节点比较，直到 <= 父节点。整个建立大根堆的过程可以简单理解为大数上浮
排序（小数下沉）：将根节点（此时为最大值）与末尾交换（此时末尾部分有序），末尾的小数交换到 root， 然后执行小数下沉的过程，再筛选出无序部分的最大值放到 root。再循环，直到所有部分有序。

堆排序的主要时间花在初始建堆期间，建好堆后，堆这种数据结构以及它奇妙的特征，使得找到数列中最大的数字这样的操作只需要O(1)的时间复杂度，维护需要logn的时间复杂度。堆排序不适宜于记录数较少的文件

性能：时间复杂度O(nlohn), 空间复杂度O(1)

  public static void heapSort(int[] arr) {
   
    if (arr == null || arr.length < 2) return;
    for (int i = 0; i < arr.length; i++) {
   
      heapUp(arr, i);
    }
    int size = arr.length;
    for (int i = 0; i < arr.length; i++) {
   
      swap(arr, 0, --size);
      heapDown(arr, 0, size);
    }
  }

  //大数上浮
  private static void heapUp(int[] arr, int index) {
   
    while (index > 0) {
   
      if (arr[index] <= arr[(index - 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20