域名138查询网_东莞网站制作与网站建设_抖音关键词排名优化_西安竞价托管

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点.

先上代码 

public class HeapSort {void  heapSort(int A[]){if (A == null || A.length <= 1) {return;}int n = A.length;// 1. 构建最大堆（从最后一个非叶子节点开始）for (int i = (n - 1) / 2; i >= 0; i--) {heapify(A, n, i);}// 2. 进行堆排序for (int i = n - 1; i >= 0; i--) {swap(A, 0, i);  // 交换堆顶和最后一个元素heapify(A, i, 0);  // 重新调整堆}}// 调整堆（维护堆的性质）private void heapify(int[] A, int heapSize, int parentIndex) {int largest = parentIndex;int leftChild = 2 * parentIndex + 1;int rightChild = 2 * parentIndex + 2;// 检查左子节点if (leftChild < heapSize && A[leftChild] > A[largest]) {largest = leftChild;}// 检查右子节点if (rightChild < heapSize && A[rightChild] > A[largest]) {largest = rightChild;}// 如果最大值发生变化，交换并递归调整if (largest != parentIndex) {swap(A, parentIndex, largest);heapify(A, heapSize, largest);}}// 交换两个数组元素private void swap(int[] A, int i, int j) {int temp = A[i];A[i] = A[j];A[j] = temp;}
}

以数组A = {4, 6, 8, 5, 9}为例 

在其调整之后 

        9
       /   \
      6     8   调整后变为                           
     / \
    5   4                          

         4
       /   \
      6     8
     / 
    5   9 (已排序) 那么首先第一个问题便是

为什么不能直接使用 heapAdjust(A, n, 0); 来构建大顶堆，而是要用 for(int i = (n-1)/2; i >= 0; i--) heapAdjust(A, n, i);

只对 heapAdjust(A, n, 0); 进行一次调用，它仅调整 A[0] 这一棵子树，但不会处理整个数组形成的堆结构，导致并不是所有子树都符合最大堆的定义

构建大顶堆需要同时满足左子树和右子树小于堆顶的元素 若从A[0]开始进行遍历 并且开始递归 只能保证一侧的子树满足要求 而不能保证左子树和右子树同时满足 因为堆排序是类似于完全二叉树的结构 所以需要进行从最后一个非叶子节点 i = (n-1)/2 开始，依次向上调整堆，保证每个子树都符合最大堆的定义，最终整个数组成为一个合法的最大堆.

那么又会有第二个问题

进行堆调整 for(int j=n-1;j>=0;j--)

{ swap(A,j,0);

heapAjust(A,j,0);

}堆调整只需要从0开始呢而不是从 j/2 开始呢

删除堆顶（交换 A[0] 和 A[j]） 之后，A[0] 可能不再是最大值，需要调整。 但 堆的其他部分（A[1] ~ A[j-1]）仍然是最大堆，只有 A[0] 可能破坏堆结构。 只需要让 A[0] 向下调整，恢复最大堆。

只需要 heapAdjust(A, j, 0); 只让 A[0] 下沉，保持 A[0] ~ A[j-1] 的最大堆性质。

这比 for (int i = j/2; i >= 0; i--) 更高效，因为只用调整 A[0]，不需要重新遍历整个堆 那也就是说 如果交互从i=j/2也没有错 只不过是多加计算了 没有任何意义 没有调整的一侧根本不需要改变 因为在构建堆的时候已经比较过了 即调整的意义在于不会遍历整个堆 只会让堆的一侧进行运算 因为只修复 A[0]，不影响其他节点 所以不可能访问所有的非叶子节点  即最优解是最优解是 heapAdjust(A, j, 0);