堆排序的思路与常见的标题

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

1. public class HeapSort {
3.     void  heapSort(int A[])
4.     {
5.         if (A == null || A.length <= 1) {
6.             return;
7.         }
8.         int n = A.length;
9.         // 1. 构建最大堆（从最后一个非叶子节点开始）
10.         for (int i = (n - 1) / 2; i >= 0; i--) {
11.             heapify(A, n, i);
12.         }
14.         // 2. 进行堆排序
15.         for (int i = n - 1; i >= 0; i--) {
16.             swap(A, 0, i);  // 交换堆顶和最后一个元素
17.             heapify(A, i, 0);  // 重新调整堆
18.         }
19.     }
20.     // 调整堆（维护堆的性质）
21.     private void heapify(int[] A, int heapSize, int parentIndex) {
22.         int largest = parentIndex;
23.         int leftChild = 2 * parentIndex + 1;
24.         int rightChild = 2 * parentIndex + 2;
26.         // 检查左子节点
27.         if (leftChild < heapSize && A[leftChild] > A[largest]) {
28.             largest = leftChild;
29.         }
31.         // 检查右子节点
32.         if (rightChild < heapSize && A[rightChild] > A[largest]) {
33.             largest = rightChild;
34.         }
36.         // 如果最大值发生变化，交换并递归调整
37.         if (largest != parentIndex) {
38.             swap(A, parentIndex, largest);
39.             heapify(A, heapSize, largest);
40.         }
41.     }
43.     // 交换两个数组元素
44.     private void swap(int[] A, int i, int j) {
45.         int temp = A[i];
46.         A[i] = A[j];
47.         A[j] = temp;
48.     }
49. }

复制代码

以数组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);

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。