java - 实现堆排序的正确方法是什么？

Question

我花了 5 个小时看了这么多视频和阅读 Material (包括 cormen)，我最终决定编写自己的堆排序来测试它。我基本上是从标准输入中获取一些输入并将它们存储在一个数组中，然后我将使用堆排序对它们进行排序。

以下是我的代码

 public static void buildHeap(int[] A)
     {
         n = A.length - 1;
         for(int i = n/2; i>0; i--)
         {
             maxHeapify(A,i);
         }
     }

     public static void maxHeapify(int[] A, int i)
     {
         int left = 2*i;
         int right = 2*i + 1;
         int largest = 0;
         if(left <= n && A[left] > A[i])
            {
                largest=left;
            }
            else
            {
                largest=i;
            }

            if(right <= n && A[right] > A[largest]){
                largest=right;
            }
            if(largest!=i){
                int temp = A[i];
                A[i] = A[largest];
                A[largest] = temp;
                maxHeapify(A, largest);
            }
        }

My Array Input is : 3,5,8,7,1,13,11,15,6 Output is: 3,15,13,11,6,8,5,7,1

输出显然是错误的，因为第一个索引应该包含最高值 15。

然后我决定采用老式的方法，拿起笔和笔记本并跟踪代码，并意识到在 buildHeap 中 i 应该是 n-1/2 。但是它也没有给我正确的输出。我现在真的很迷茫，很沮丧。谁能阐明我做错了什么？

Answer 1

您的索引计算已关闭:

int left = 2*i;
int right = 2*i + 1;

如果 i 为 0，那么我们希望 left 和 right 为 1 和 2。如果 i为 1，则 left 和 right 应为 3 和 4，依此类推。计算应该是:

int left = 2*i + 1;
int right = 2*i + 2;

此外，

for(int i = n/2; i>0; i--)

条件是i > 0。循环体只会在 i > 0 时运行，因此索引 0 处的元素(即第一个元素)不会被移动。条件应为 i >= 0。