Java ArrayList快速排序算法异常，请求排查帮助

问题现象 #

测试用例排序前：[9, 2, 10, 3, 6, 7, 4, 8, 5, 1]
排序后结果：[1, 2, 5, 3, 4, 6, 7, 8, 9, 10]，可见中间部分元素未完成正确排序。

核心错误分析 #

1. Pivot取值完全错误 #

partition方法中，quicksort.getRandom(quickList)返回的是随机索引，但代码直接将该索引值转为int作为pivot数值进行比较，这完全违背逻辑——应该获取该索引对应的元素值作为pivot，而非索引本身。

2. 泛型比较逻辑错误 #

代码中使用强制类型转换(int) quickList.get(length)进行数值比较，既破坏了泛型的通用性，也可能引发类型转换异常，正确的做法是使用Comparable接口的compareTo方法。

3. Partition循环边界错误 #

• 左指针循环条件length > begin应改为length >= begin，否则会跳过对起始位置元素的检查；
• 右指针循环条件init < end应改为init <= end，否则会跳过对结束位置元素的检查；
• 缺少将pivot元素交换到最终正确位置的步骤，导致递归划分的边界错误。

4. 中位数选择方法逻辑错误 #

quicksort.getMedian方法仅基于数组长度计算中间索引，未对元素进行排序，这不是真正的中位数元素索引；且奇数长度分支仅打印元素，未返回值，编译时会报错。

修复后的完整代码 #

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

public class QuickSortFix {

    static <T extends Comparable<? super T>> void quickSort(ArrayList<T> quickList, int begin, int end) {
        if (begin < end) {
            int partitionIndex = partition(quickList, begin, end);

            quickSort(quickList, begin, partitionIndex - 1);
            quickSort(quickList, partitionIndex + 1, end);
        }
    }

    private static <T extends Comparable<? super T>> int partition(ArrayList<T> quickList, int begin, int end) {
        // 修复：获取当前子数组内的随机索引对应的元素作为pivot
        int pivotIndex = QuickSortStrategy.getRandom(quickList, begin, end);
        T pivot = quickList.get(pivotIndex);
        // 先将pivot交换到子数组末尾，简化partition逻辑
        swap(quickList, pivotIndex, end);
        
        int left = begin;
        int right = end - 1;

        while (left <= right) {
            // 使用compareTo进行泛型比较，修复强制类型转换问题
            while (left <= right && quickList.get(left).compareTo(pivot) < 0) {
                left++;
            }
            while (left <= right && quickList.get(right).compareTo(pivot) > 0) {
                right--;
            }
            if (left <= right) {
                swap(quickList, left, right);
                left++;
                right--;
            }
        }
        // 将pivot交换到最终正确位置
        swap(quickList, left, end);
        return left;
    }

    private static <T> void swap(ArrayList<T> list, int i, int j) {
        T temp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, temp);
    }

    // 重构pivot选择策略，修复原接口的逻辑错误
    public interface QuickSortStrategy {
        /**
         * 获取当前子数组的中位数元素索引（基于元素排序）
         */
        static <T extends Comparable<? super T>> int getMedian(ArrayList<T> list, int begin, int end) {
            int mid = begin + (end - begin) / 2;
            T a = list.get(begin);
            T b = list.get(mid);
            T c = list.get(end);
            // 比较三个位置的元素，返回中位数对应的索引
            if ((a.compareTo(b) >= 0 && a.compareTo(c) <= 0) || (a.compareTo(b) <= 0 && a.compareTo(c) >= 0)) {
                return begin;
            } else if ((b.compareTo(a) >= 0 && b.compareTo(c) <= 0) || (b.compareTo(a) <= 0 && b.compareTo(c) >= 0)) {
                return mid;
            } else {
                return end;
            }
        }

        /**
         * 在当前子数组范围内获取随机索引
         */
        static <T> int getRandom(ArrayList<T> list, int begin, int end) {
            Random rand = new Random();
            return begin + rand.nextInt(end - begin + 1);
        }

        /**
         * 从当前子数组中选三个随机元素，取其中位数索引
         */
        static <T extends Comparable<? super T>> int getThreeRandomThenMedian(ArrayList<T> list, int begin, int end) {
            int idx1 = getRandom(list, begin, end);
            int idx2 = getRandom(list, begin, end);
            int idx3 = getRandom(list, begin, end);
            T a = list.get(idx1);
            T b = list.get(idx2);
            T c = list.get(idx3);
            if ((a.compareTo(b) >= 0 && a.compareTo(c) <= 0) || (a.compareTo(b) <= 0 && a.compareTo(c) >= 0)) {
                return idx1;
            } else if ((b.compareTo(a) >= 0 && b.compareTo(c) <= 0) || (b.compareTo(a) <= 0 && b.compareTo(c) >= 0)) {
                return idx2;
            } else {
                return idx3;
            }
        }
    }

    // 测试方法
    public static void main(String[] args) {
        ArrayList<Integer> testList = new ArrayList<>(Arrays.asList(9, 2, 10, 3, 6, 7, 4, 8, 5, 1));
        System.out.println("排序前：" + testList);
        quickSort(testList, 0, testList.size() - 1);
        System.out.println("排序后：" + testList);
    }
}

修复说明 #

1. Pivot处理：先将随机选中的pivot元素交换到子数组末尾，简化partition逻辑，最后再将pivot交换到正确的划分位置；
2. 泛型比较：使用compareTo方法替代强制类型转换，保证代码的通用性和安全性；
3. 边界修正：调整循环边界，确保所有元素都被检查；
4. 策略重构：修改pivot选择策略，使其基于当前子数组（而非整个数组）进行计算，修复中位数选择的逻辑错误；
5. 新增swap工具方法：简化元素交换代码，提高可读性。

测试结果 #

排序前：[9, 2, 10, 3, 6, 7, 4, 8, 5, 1]
排序后：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

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