Java绑定Comparable的泛型堆排序方法传入Integer[]报类转换异常

定义了如下泛型类：

public class HeapClass <E extends Comparable <E>>

类中包含堆排序方法：

public void heapSort(E[] arr)

编写main方法测试，传入Integer数组调用排序方法：

Integer[] arr = {3, 2, 1, 4};
        
HeapClass h = new HeapClass();
        
h.heapSort(arr);

运行时抛出如下异常：

Exception in thread "main" java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.Comparable;
    at HeapClass.heapSort(HeapClass.java:11)
    at Test.main(Test.java:9)

两个文件的完整代码如下：

HeapClass.java #

public class HeapClass <E extends Comparable <E>>
{
    private int lastposition;
    
    private E[] array;
    
    public void heapSort(E[] arr)
    {
        lastposition = arr.length - 1;
        
        array = (E[]) new Object[arr.length * 2];
        
        for (int i = 0; i < arr.length; i++)
            add(arr[i]);
        
        for (int i = 0; i < arr.length; i++)
            array[arr.length - i - 1] = remove();
        
        arr = array;
    }
    
    public void add (E obj)
    {
        lastposition++;
        array[lastposition] = obj;
        trickleUp(lastposition);
    }
    
    public void swap (int from, int to)
    {
        E temp = array[from];
        array[from] = array[to];
        array[to] = temp;
    }
    
    public void trickleUp(int position)
    {
        if (position == 0)
            return;
        
        int parent = (int) Math.floor((position - 1) / 2);
        
        if (((Comparable <E>) array[position]).compareTo(array[parent]) > 0)
        {
            swap(position, parent);
            trickleUp(parent);
        }
    }
    
    public E remove()
    {
        E temp = array[0];
        swap(0, lastposition--);
        trickleDown(0);
        return temp;
    }
    
    public void trickleDown(int parent)
    {
        int left = 2 * parent + 1;
        int right = 2 * parent + 2;
        
        if (left == lastposition && ((Comparable <E>) array[parent]).compareTo(array[left]) < 0)
        {
            swap(parent, left);
            return;
        }
        if (left == lastposition)
            return;
        if (right == lastposition)
        {
            E max;
            int pos;
            if (((Comparable <E>) array[left]).compareTo(array[right]) < 0)
            {
                max = array[right];
                pos = 1;
            }
            else
            {
                max = array[left];
                pos = 0;
            }
            
            if(((Comparable <E>) array[parent]).compareTo(max) < 0)
            {
                if (pos == 0)
                {
                    swap(parent, left);
                    return;
                }
                else
                {
                    swap(parent, right);
                    return;
                }
            }
            return;
        }
        if (left >= lastposition || right >= lastposition)
            return;
        if (((Comparable <E>) array[left]).compareTo(array[right]) > 0 && ((Comparable <E>) array[parent]).compareTo(array[left]) < 0)
        {
            swap(parent, left);
            trickleDown(left);
        }
        if (((Comparable <E>) array[parent]).compareTo(array[right]) < 0)
        {
            swap(parent, right);
            trickleDown(right);
        }
    }

}

Test.java #

public class Test
{
    public static void main (String[] args)
    {
        Integer[] arr = {3, 2, 1, 4};
        
        HeapClass h = new HeapClass();
        
        h.heapSort(arr);
        
        for (int i = 0; i < arr.length; i++)
            System.out.println(arr[i]);
        
    }
}

异常原因 #

• 直接触发报错的原因：Java泛型存在类型擦除机制，该类中类型参数E的上界是Comparable<E>，擦除后E对应的运行时类型为Comparable。代码中array = (E[]) new Object[arr.length * 2];创建的是Object类型数组，Object[]和Comparable[]不存在继承关系，强制类型转换必然抛出ClassCastException。
• 代码还存在两个隐藏逻辑问题：
  • Java中引用类型参数是值传递，方法内修改形参的引用指向不会影响外部实参。方法末尾的arr = array;属于无效代码，就算不报错，main方法中的原数组也不会被修改，最终打印的还是未排序的原始数据。
  • 内部创建的数组长度是原数组的2倍，和入参数组长度不匹配，赋值后会出现数组长度不符合预期的问题。

修复方案 #

1. 替换错误的数组创建逻辑：不要通过new Object[]强转得到泛型数组，通过反射创建和入参数组元素类型一致的数组，从根源避免类型转换异常。
2. 删除无效的形参赋值逻辑：排序完成后，将内部数组的排序结果拷贝回传入的原数组，保证外部实参可以拿到正确的排序结果。
3. 将内部数组长度调整为和入参数组一致，避免长度不匹配问题。

修复后的核心代码 #

修改heapSort方法：

public void heapSort(E[] arr)
{
    lastposition = -1;
    // 创建和入参元素类型一致的数组，避免类型转换异常
    array = (E[]) java.lang.reflect.Array.newInstance(arr.getClass().getComponentType(), arr.length);

    for (int i = 0; i < arr.length; i++)
        add(arr[i]);

    for (int i = 0; i < arr.length; i++)
        array[arr.length - i - 1] = remove();

    // 将排序结果拷贝回原数组
    System.arraycopy(array, 0, arr, 0, arr.length);
}

测试类中创建实例时补充泛型参数，避免原始类型警告：

HeapClass<Integer> h = new HeapClass<>();

修复后运行代码，即可正确输出升序排列的结果：1、2、3、4。

内容的提问来源于stack exchange，提问作者Brian O