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

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

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

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

如图1是一个没有通过调整的堆
.net

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

图三：

图四：

图五：

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

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;
    }

这里面用到了递归，由于调整堆的时候三个元素一个调整，可是调整了上面下面的对有可能就乱了，因此须要一直向下调整xml

堆调整好了以后只须要将堆顶元素和堆最后一个元素进行替换而后调整blog

如图：


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

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

完整程序：递归

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);
        }
    }
}

堆排序的时间复杂度：
因为堆排序是由两部分(堆调整 + 堆排序)完成的，因此时间复杂度也应该是两部分之和。图片

首先堆调整，堆调整的时间复杂度为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