java - 在java代码中进行堆排序？

Question

我正在尝试在 java 中进行一些堆排序以获取乐趣。

首先，我创建了一个最大堆。然后取第一个元素到变量max，将最后一个元素从未排列的数组中移到堆顶，然后下推。

我尝试了 21 个元素，70% 的时间都可以正常工作，我想知道是否有人发现了问题。

谢谢。

public class HeapSort extends Sort{
    public int sort(int arr[]) {
        for (int i = 1; i < arr.length; i++) {
            // add to heap
            int p = i;
            int pp = p /2 ;
            while (p > 0 && arr[pp] < arr[p]) {
                swap(arr, p, pp);
                p = pp;
                pp = p / 2;
            }

        }   

        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            int p = 0;
            int child1 = (p << 1) + 1;
            int child2 = (p << 1) + 2;

            while (child2 < i || child1 < i) {
                if (child1 >= i) {
                    if (arr[p] < arr[child2]) {
                        swap(arr, p, child2);
                        p = child2;
                    } else { 
                        break;
                    }
                } else if (child2 >= i) {
                    if (arr[p] < arr[child1]) {
                        swap(arr, p, child1);
                        p = child1;
                    } else {
                        break;
                    }
                } else {
                    int minIdx = arr[child1] < arr[child2] ? child1 : child2;
                    int maxIdx = child1 == minIdx ? child2 : child1;

                    if (arr[p] < arr[maxIdx]) {
                        swap(arr, p, maxIdx);
                        p = maxIdx;
                    } else {

                        break;

                    }
                }
                child1 = (p << 1) + 1;
                child2 = (p << 1) + 2;
            }

        }
        return 0;

    }
    void swap(int arr[], int idx1, int idx2) {
        int tmp = arr[idx1]; arr[idx1] = arr[idx2]; arr[idx2] = tmp;
    }
    public String toString() {
        return "HeapSort";
    }

}

Answer 1

在堆排序的第一步中，您没有正确构建堆。在基于零的数组上除以二之前，您需要减去一。

public class HeapSort extends Sort{ 
   public int sort(int arr[]) { 
      for (int i = 1; i < arr.length; i++) { // add to heap 
         int p = i;
         // int pp = p /2 ;  <======= Problem!
         int pp = (p-1) / 2; 
         while (p > 0 && arr[pp] < arr[p]) { 
            swap(arr, p, pp); p = pp; 
            //  pp = p / 2; // <=====Problem!
            pp = (p-1) /2;

}