Java泛型ArrayList快速排序方法类型错误排查求助

核心错误分析 #

• ArrayList元素访问方式错误：Java里ArrayList<T>是集合类，不能像数组那样用arr[index]语法获取元素，必须调用get(int index)方法。你写的arr[pivotIndex]是数组的访问语法，编译器会误以为arr是数组类型，但实际是ArrayList<T>，因此抛出类型不匹配错误。
• pivot类型与partition参数不匹配：你的泛型是T extends Comparable<? super T>，pivot是ArrayList中的元素，类型应该是T而非int；同时你声明的partition方法最后一个参数是int，这和实际要传入的pivot类型完全不匹配，必须改成T。

修正后的代码示例 #

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

public class QuickSortUtil {
    public static <T extends Comparable<? super T>> void quicksort(ArrayList<T> arr, int start, int end) {
        if (start >= end) {
            return;
        }

        // 修正nextInt范围，确保pivotIndex能取到end索引，避免越界
        int pivotIndex = new Random().nextInt(end - start + 1) + start;
        T pivot = arr.get(pivotIndex); // 改用get方法获取元素，类型改为泛型T
        swap(arr, pivotIndex, end);

        // partition方法最后一个参数现在为T类型，匹配pivot的类型
        int leftPointer = partition(arr, start, end, pivot);

        quicksort(arr, start, leftPointer - 1);
        quicksort(arr, leftPointer + 1, end);
    }

    // 辅助交换方法，针对ArrayList实现
    private static <T> void swap(ArrayList<T> arr, int i, int j) {
        T temp = arr.get(i);
        arr.set(i, arr.get(j));
        arr.set(j, temp);
    }

    // 修正后的partition方法签名及示例实现
    private static <T extends Comparable<? super T>> int partition(ArrayList<T> arr, int start, int end, T pivot) {
        int left = start;
        int right = end - 1;

        while (left <= right) {
            // 用compareTo方法比较泛型元素大小
            while (left <= right && arr.get(left).compareTo(pivot) <= 0) {
                left++;
            }
            while (left <= right && arr.get(right).compareTo(pivot) > 0) {
                right--;
            }
            if (left < right) {
                swap(arr, left, right);
            }
        }
        swap(arr, left, end);
        return left;
    }
}

额外注意点 #

• 原代码中new Random().nextInt(end - start)生成的是[0, end-start)范围的整数，计算后pivotIndex最大为end-1，如果需要包含end索引，要改成nextInt(end - start + 1)，避免索引越界。
• partition方法内部必须使用compareTo方法来比较泛型元素的大小，不能直接用数值比较符。

内容的提问来源于stack exchange，提问作者Preston Little