排序算法-堆排序和时间复杂度_堆排序的时间复杂度

堆排序分为两个部分：堆调整+堆排序
堆排序的思路：将一个已知的序列先调整到大堆的形式，然后再将堆顶元素和堆最后的元素进行调换（这样最大的元素就在最后面了），减去最后一个元素将剩余的元素进行堆调整，重复上面的步骤就会生成从小到大的序列。

这里牵扯到两个概念，一个是调整大堆，另一个是对堆顶元素和最后一个元素调换的理解

首先，先来看调整大堆
调整大堆的核心思路是：找到parent，rchild,lchild,将rchild,lchild中最大的和parent进行替换，(如果parent > 两个孩子说明不需要进行调整，直接退出)替换后还要调整下面的堆所以将parent指向刚才与parent进行替换的孩子，计算此时的lchild和rchild，一直重复知道左孩子或右孩子大于序列的下标。

如图1是一个没有经过调整的堆

图二:假设节点数是n,那么就从parent = n/2 -1开始进行堆排序。之后parent–;

图三：

图四：

图五：

这样就算完成第一步堆的调整

public void BigHeadAdjust(Element[] elements,int parent,int size){
        int lchild = 2 * parent + 1;
        int rchild = 2 * parent + 2;
        int child = lchild;
        /**
         * A.compareTo(B) > 0 表示A > B 返回大于零
         */
        if(rchild < size && elements[rchild].compareTo(elements[lchild]) > 0){
            child = rchild;
        }
        if(lchild < size && elements[child].compareTo(elements[parent]) > 0){
            Element temp = elements[child];
            elements[child] = elements[parent];
            elements[parent] = temp;
            BigHeadAdjust(elements,child,size);
        }
        return;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这里面用到了递归，因为调整堆的时候三个元素一个调整，但是调整了上面下面的堆有可能就乱了，所以需要一直向下调整

堆调整好了之后只需要将堆顶元素和堆最后一个元素进行替换然后调整

如图：


基本过程就是和上图一样，一直进行替换、调整、替换、调整直到堆顶元素。

for(int i = elements.length - 1; i > 0; i--){
            Element temp = elements[0];
            elements[0] = elements[i];
            elements[i] = temp;
            BigHeadAdjust(elements,0,i);
        }
1
2
3
4
5
6

完整程序：

public class HeapSorter implements Sorter {
    public void BigHeadAdjust(Element[] elements,int parent,int size){
        int lchild = 2 * parent + 1;
        int rchild = 2 * parent + 2;
        int child = lchild;
        /**
         * A.compareTo(B) > 0 表示A > B 返回大于零
         */
        if(rchild < size && elements[rchild].compareTo(elements[lchild]) > 0){
            child = rchild;
        }
        if(lchild < size && elements[child].compareTo(elements[parent]) > 0){
            Element temp = elements[child];
            elements[child] = elements[parent];
            elements[parent] = temp;
            BigHeadAdjust(elements,child,size);
        }
        return;
    }
    @Override
    public void sort(Element[] elements) {
        //TODO
        for(int i = elements.length/2 - 1; i >= 0; i --){
            BigHeadAdjust(elements,i,elements.length);
        }
        for(int i = elements.length - 1; i > 0; i--){
            Element temp = elements[0];
            elements[0] = elements[i];
            elements[i] = temp;
            BigHeadAdjust(elements,0,i);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

堆排序的时间复杂度：
由于堆排序是由两部分(堆调整 + 堆排序)完成的，所以时间复杂度也应该是两部分之和。

首先堆调整，堆调整的时间复杂度为O(n)
假设堆高度为K,从倒数第二层开始每个节点都需要进行与子节点的比较，也就是要进行堆调整，所以计算如下

堆排序的时间复杂度为O(nlogn)
假设节点数为n,所以需要进行n - 1次调换，也就是需要n-1次堆调整，每次堆调整的时间复杂度为O(logn) ，那么总的时间复杂度就是(n - 1)O(logn) = O(nlogn)

最后堆排序的时间复杂度为：
O(n) + O(nlogn) = O(nlogn)

关于时间复杂度可以参考下面文章：
https://blog.csdn.net/qq_34228570/article/details/80024306