java - 应用 Java 实现的 HeapSort 后列表未排序

Question

我试图在java中实现heapSort，但执行后没有得到排序列表。你能建议我在这里做错了什么吗？我创建了一个方法 Heapsort 来对调用堆本身的堆进行排序。一旦调用堆，它就会给我一个堆树，其中包含顶部的最大元素。我假设我的交换或进一步的过程无法正常工作。这里出了什么问题？

  public class HeapSort 
  {
   public static void main(String args[])
   {
    int a[]=new int[]{30,100,20,80,40,90,50,60};
    for(int i=0;i<a.length;i++)
    {
        System.out.print(a[i]+"\t");
    }
    System.out.println("");
    heapSort(a);
    for(int i=0;i<a.length;i++)
    {
        System.out.print(a[i]+"\t");
    }
}
public static void heapSort(int a[])
{
    int i, temp;
    for(i=a.length-1;i>=0;i--)
    {
        heap(a);
        temp=a[0];
        a[0]=a[i];
        a[i]=temp;
    }
}
public static void heap(int a[])
{
    int i,j,k,temp;
    for(i=0;i<a.length;i++)
    {
        j=i;
        k=(i-1)/2;
        while(k>=0&&a[j]>a[k])
        {
            temp=a[j];
            a[j]=a[k];
            a[k]=temp;
            j=j/2;
            k=k/2;
        }
    }
}
}

Answer 1

您应该尝试调试您的代码。

或者您可以采用旧方式，并插入打印语句，这样您就可以在中间结果中看到模式。

在 heap() 的开头和结尾添加打印语句方法:

public static void heap(int a[])
{
    System.out.println("heap in : " + Arrays.toString(a));
    // existing code
    System.out.println("heap out: " + Arrays.toString(a));
}

输出

heap in : [30, 100, 20, 80, 40, 90, 50, 60]
heap out: [100, 90, 80, 60, 40, 20, 50, 30]
heap in : [30, 90, 80, 60, 40, 20, 50, 100]
heap out: [100, 90, 80, 60, 40, 20, 50, 30]
heap in : [50, 90, 80, 60, 40, 20, 100, 30]
heap out: [90, 60, 100, 50, 40, 20, 80, 30]
heap in : [20, 60, 100, 50, 40, 90, 80, 30]
heap out: [100, 90, 80, 30, 40, 60, 50, 20]
heap in : [40, 90, 80, 30, 100, 60, 50, 20]
heap out: [90, 100, 80, 30, 40, 60, 50, 20]
heap in : [30, 100, 80, 90, 40, 60, 50, 20]
heap out: [100, 90, 80, 30, 40, 60, 50, 20]
heap in : [80, 90, 100, 30, 40, 60, 50, 20]
heap out: [100, 80, 90, 30, 40, 60, 50, 20]
heap in : [80, 100, 90, 30, 40, 60, 50, 20]
heap out: [100, 80, 90, 30, 40, 60, 50, 20]

你看到问题了吗？

堆排序应该将最大值推到最后一个位置，然后将第二大的值推到倒数第二个位置，依此类推...

但是，100继续前进。为什么？因为您将整个数组发送到 heap() 每次通话。

更改自 heap(int a[])至heap(int a[], int len) .
替换i<a.length与 i<len在heap方法。
更改heap(a);至heap(a, i + 1);在heapSort方法。

问题已解决。