算法系列四：堆排序
一、原理
1.大根堆得最大值
将待排序数组所有数据创建成大根堆排列，排出数组首元素为数组中的最大值，将数组最大值排放到数组末尾总体完成它一个数据的排列
2.新堆得接下来最大值
交换排序好后整体堆的结构被破坏，因为数组中的最大值找到并放到了数组末尾完成了它数据的排列，接下来重新维护出堆得最大值排序就是要得此最大值之外剩余数据中的最大值即第二大的值接着放到第一大值前面这样来进行排序的，所以接下来继续维护出堆得最大值就去包含已排好序最大值之外剩下的接下来的最大值，所以回到堆结构被破坏，此时要再维护出堆得接下来的最大值维护的堆就不再包含那些得到交换下来的过去最大值了，不包含它们以后，去维护的此时新堆就为交换到堆顶数据一个破坏点其它全堆的结构，用一次向下调整就能维护出继续出接下来最大值再往后放成最大值们的升序排放，最后，所有数据最大值、剩余数据最大值、再剩余数据最大值、所有再剩余数据最大值都堆排比较找出并排放好后，数组就整体排好序了
二、实现
1.createBigHeap、siftDown
建大根堆、向下调整维护建堆： 【数据结构】堆
2.end
- end即当前维护堆的最大值出来后放的当前堆的堆末位置，与堆顶最大值交换完后紧接着做当前接下来向下调整创新堆的堆末不包含边界位置参考，新堆创好后，end再移动指向当前新堆的堆末位置再给交换
end＝0时即数组0、1下标前两个元素建的堆最大值前后交换完之后以1为堆边界又去建只有首元素的新堆(虽然函数调用了但里面没去调整重新建堆)，然后end--指向此只有一个首元素堆的堆末，此时数组就只剩一个其它都去已排好序的首元素了它也就是排好序的不用排了，一共进行n-1次向下调整维护堆
2.升序降序
- 建大堆的得最大值往最后放成的是升序排列
- 建小堆的得最小值往最后放成的是降序排列
3.代码参考：
public static void heapSort(int[] array) {
createBigHeap(array);
int end = array.length-1;
while (end > 0) {
swap(array,0,end);
siftDown(array,0,end);
end--;
}
}
private static void createBigHeap(int[] array) {
for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {
siftDown(array,parent,array.length);
}
}
private static void siftDown(int[] array,int parent,int end) {
int child = 2*parent+1;
while (child < end) {
if(child + 1 < end && array[child] < array[child+1]) {
child++;
}
if(array[child] > array[parent]) {
swap(array,child,parent);
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}
private static void swap(int[] array,int i,int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}三、性质
1.时间复杂度
- 首先最开始创建一个全元素的整体大根堆建堆需要O(n)的时间：从下往上一个个节点向下转型建堆时下层的节点虽然多但向下调整的高度低、上层的节点虽然调整高度高但去调整的节点少，综合下来是O(n)的时间复杂度
- n-1个的堆顶元素向下调整维护堆每个需要log2(n)当前堆树的高度向下移动次数，所以n-1个节点的向下调整维护堆的时间为(n-1)*log2(n)
所以总的时间复杂度为n+(n-1)log2(n)，算为O(n*log2(n))，但实际上n-1个堆顶元素去向下调整维护堆时它们维护的堆树是越来越小越来越矮的，因为维护的堆树的n节点在越来越少，所以每个节点去算以log2(n)的移动调整次数是偏多的，实际上时间复杂度还要再小，堆排序是所有排序中速度最快的
树高度计算的补充：
- 这里默认堆顶首节点层的高度记为0的，树的高度为log2(n)的向下取整
- 如果堆顶首节点层的高度以1开始计算的，那么树的高度为log2(n+1)的向上取整
2.空间复杂度
空间复杂度O(1)
3.稳定性
不稳定的排序