堆排序算法详解
原理
1. 大根堆的最大值
将待排序数组所有数据创建成大根堆排列，排出数组首元素为数组中的最大值，将数组最大值排放到数组末尾，完成一个数据的排列。
2. 新堆的接下来最大值
交换排序后整体堆的结构被破坏。因为数组中的最大值找到并放到了数组末尾完成了它数据的排列，接下来重新维护出堆的最大值。排序就是要得此最大值之外剩余数据中的最大值即第二大的值接着放到第一大值前面这样来进行排序的。所以接下来继续维护出堆的最大值就去包含已排好序最大值之外剩下的接下来的最大值。所以回到堆结构被破坏，此时要再维护出堆的接下来的最大值，维护的堆就不再包含那些得到交换下来的过去最大值了。不包含它们以后，去维护的此时新堆就为交换到堆顶数据的一个破坏点其它全堆的结构，用一次向下调整就能维护出继续出接下来最大值再往后放成最大值们的升序排放。最后，所有数据最大值、剩余数据最大值、再剩余数据最大值、所有再剩余数据最大值都堆排比较找出并排放好后，数组就整体排好序了。
实现
1. createBigHeap、siftDown
建大根堆、向下调整维护建堆。
2. end 逻辑
end 即当前维护堆的最大值出来后放的当前堆的堆末位置，与堆顶最大值交换完后紧接着做当前接下来向下调整创新堆的堆末不包含边界位置参考。新堆创好后，end 再移动指向当前新堆的堆末位置再给交换。
当 end = 0 时，即数组 0、1 下标前两个元素建的堆最大值前后交换完之后以 1 为堆边界又去建只有首元素的新堆（虽然函数调用了但里面没去调整重新建堆），然后 end-- 指向此只有一个首元素堆的堆末，此时数组就只剩一个其它都去已排好序的首元素了它也就是排好序的不用排了，一共进行 n-1 次向下调整维护堆。
3. 升序降序
- 建大堆的得最大值往最后放成的是升序排列
- 建小堆的得最小值往最后放成的是降序排列
4. 代码参考
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 {
( (array.length - - ) / ; parent >= ; parent--) {
siftDown(array, parent, array.length);
}
}
{
* parent + ;
(child < end) {
(child + < end && array[child] < array[child + ]) {
child++;
}
(array[child] > array[parent]) {
swap(array, child, parent);
parent = child;
child = * parent + ;
} {
;
}
}
}
{
array[i];
array[i] = array[j];
array[j] = tmp;
}
