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

Question

我花了最后 5 个小时看了这么多视频和阅读材料（包括 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.

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

What is the correct way of implementing the heapsort?

java

algorithm

heapsort