1

我正在尝试学习堆排序。我遵循伪代码指令，但是，我的程序无法正常工作。我现在已经调试了一个小时，找不到错误。有几个错误：首先，arraylist 没有正确排序；其次，arraylist 似乎是从 max -> min 排序的，即使假设它是从 min -> max 排序的。对不起初学者的问题。

import java.util.ArrayList;
import java.util.Random;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        int n;
        Scanner input = new Scanner(System.in);
        ArrayList<Integer> intList = new ArrayList<Integer>();
        Random rand = new Random();
        int minMax = 7000;

        System.out.print("Input a positive integer: ");
        n = input.nextInt();
        for (int i = 0; i < n; i++) {
            intList.add(rand.nextInt(minMax * 2) - minMax);
        }
        System.out.println(intList);
        Heapsort(intList);
        System.out.println(intList);
    }

    // Heapsort
    public static void Heapsort(ArrayList<Integer> num) {
        build_MaxHeap(num);
        int n = num.size() - 1;
        for (int i = n; i > 0; i--) {
            swap(num, 0, i);
            n = n - 1;
            max_heapify(num, 0);
        }
    }

    // build max heap from arraylist
    public static void build_MaxHeap(ArrayList<Integer> num) {
        for (int i = (num.size() - 1) / 2; i >= 0; i--)
            max_heapify(num, i);
    }

    // max heapify
    public static void max_heapify(ArrayList<Integer> num, int i) {
        int left = 2 * i;
        int right = 2 * i + 1;
        int max = i;
        int n = num.size() - 1;
        if (left <= n && num.get(left) > num.get(i))
            max = left;
        if (right <= n && num.get(right) > num.get(max))
            max = right;

        if (max != i) {
            swap(num, i, max);
            max_heapify(num, max);
        }
    }

    // swap 2 numbers in arraylist
    public static void swap(ArrayList<Integer> num, int i, int j) {
        int temp = num.get(i);
        num.set(i, num.get(j));
        num.set(j, temp);
    }
}
4

0 回答 0