heapsort 堆排序
1.基本描述
堆排序 heap sort 指利用堆这种数据结构所设计的一种排序算法。
要求完全二叉树
这边我只写最大堆
堆排序归分在选择排序。
稳定性 不稳定
时间复杂度
$$
O(nlog_2n)
$$
空间复杂度
$$
O(1)
$$
2. 最大堆进行升序排序思想：
-
初始化堆 ，将数列 [0,n-1] 构造成最大堆
-
交换数据， 将array[0]和array[n-1]交换， 然后将 array[0…n-2] 重新调整为最大堆，以此类推
-
这里有一点需要注意，无论是初始化堆，还是交换数据，都调用maxHeapDown，他的参数是 array[] , int start ,int end. 这里 三个参数一个都不能少，start 我觉得这里不好，应该形容为node节点。end可以理解，在交换数据时，需要调整的堆大小是不断变小。 start 这个参数比较微妙。我的理解是调整这个节点在其子节点中的位置，并在原来的位置替换合理的节点(注 不是他最后的位置的节点)。而由于在交换数据时，本身堆除了跟节点，就是符合最大堆特性。就像初始化堆一样，需要从底往上初始化。(这边的参数也是参考 如果天空不死)
由于已经符合，所以直接调整节点 array[0] 即可。
所以初始化堆也好，交换数据也好，本质上就是在筛选调整节点位置。这只是我的理解。,,,,堆排序初始化需要从下往上才能初始化最大堆。而交换数据相当于初始化堆的最后一步再现。
注意要点
-
for (i=n/2-1;i>=0;i--) //初始化堆 是--。从坐标最大的非叶子节点开始调节 maxheapDown(array,i,n-1); // 注意参数，遍历所有非叶节点开始的循环是 i=n/2-1 并且是i-- 循环.
这个 i 的取值 要区别 联系到 最大堆 的概念
(01) 索引为i的左孩子的索引是 (2i+1);
(02) 索引为i的左孩子的索引是 (2i+2);
(03) 索引为i的父结点的索引是 floor((i-1)/2);这个最后的非叶子节点的计算。最后一个叶子节点为 n-1 , 坐标(n-1-1)/2 =n/2-1
传入的参数是 i,n-1
-
for (i=n-1;i>0;i--){ //交换数据 int tmp=array[0]; array[0]=array[i]; array[i]=tmp; maxheapDown(array,0,i-1); // 只有根节点不符合最大堆的要求 } }for 循环从 n-1 开始。>0 是因为n-1 个数位置正确，剩下一个也正确。 i–
传入参数 0，i-1
-
3. 代码剖析
heapSortAsc
private static void heapSortAsc(int[] array) {
int i;
int n=array.length;
for (i=n/2-1;i>=0;i--) //初始化堆 是--。从坐标最大的非叶子节点开始调节
maxheapDown(array,i,n-1); // 注意参数，遍历所有非叶节点
for (i=n-1;i>0;i--){ //交换数据
int tmp=array[0];
array[0]=array[i];
array[i]=tmp;
maxheapDown(array,0,i-1); // 只有根节点不符合最大堆的要求
}
}
maxheapDown
private static void maxheapDown(int[] array,int start,int end){ //start 理解为 node 节点更好。 或者干脆改过来吧
int c=start; //调整某个节点在适当分支
int left=2*c+1; //这样0，i-1 参数更加容易理解
int tmp=array[c];
for (;left<=end;c=left,left=2*left+1){
if (left<end&&array[left]<array[left+1]) //left<end 必须放在前面
{
left++; //选择大的往上面替换。
}
if(tmp>=array[left])
break;
else {
array[c]=array[left];
array[left]=tmp; // 疑问二，tmp一直不变
}
}
}