基于MyVector的QuickSort方法异常，输出乱值请求排查

我编写了一个仅接收MyVector（本质为普通向量）作为参数的QuickSort方法，但该方法无法正常工作，不清楚问题原因。

预期输出 #

The element at index 0 is: 7
The element at index 0 is: 10
The element at index 0 is: 28

实际输出 #

The element at index 0 is: 41524
The element at index 1 is: 26432
The element at index 2 is: 51244

驱动类示例代码 #

MySort.QuickSort(testing);
System.out.println("The element at index 0 is: "+testing.elementAt(0));
System.out.println("The element at index 1 is: "+testing.elementAt(1));
System.out.println("The element at index 2 is: "+testing.elementAt(2));

原MySort类代码 #

public static void QuickSort(MyVector vec){
    MyVector lo = new MyVector();
    MyVector hi = new MyVector();
    int loSize = lo.size();
    int hiSize = hi.size();
    if (loSize >= hiSize)
        return;
    int p = (int)vec.elementAt((loSize + hiSize) / 2);   // set pivot, could use median of 3 here
    int i = loSize-1;
    int j = hiSize+1;
    while (true){
        while ((int)vec.elementAt(i) < p) {
        ++i;
        }
        while ((int)vec.elementAt(j) > p) { ;    // decrease j until a[j] <= pivot
        --j;
        }
        if (i >= j)             // break if indices meet or cross
            break;
        swap((int)vec.elementAt(i), (int)vec.elementAt(j));
    }
    QuickSort(lo);        
    QuickSort(hi); 
      }
public static void swap(int a, int b) {
    int temp;
    temp = a;
    a=b;
    b=temp;
}

问题根源分析 #

• 核心逻辑完全偏离：你在方法里新建了空的lo和hi向量，用它们的size（始终为0）来做判断、计算基准索引和循环边界，这和传入的待排序vec没有任何关联。loSize >= hiSize永远成立，直接触发return，排序代码根本没执行；就算没return，计算出的i=-1、j=1会导致访问vec的非法索引，读取到内存垃圾值，就是你看到的乱码数字。
• swap方法完全无效：Java是值传递，swap(int a, int b)交换的只是方法内部的局部变量，根本不会修改vec里的元素。
• 递归调用毫无意义：递归时传入的是空的lo和hi，完全没处理原vec的分区数据，等于白递归。

修复后的代码 #

标准快速排序采用原地排序，通过左右边界索引划分区间，不需要额外新建向量。修复后的代码如下：

public class MySort {
    // 对外暴露的入口方法
    public static void QuickSort(MyVector vec) {
        if (vec == null || vec.size() <= 1) {
            return;
        }
        quickSortHelper(vec, 0, vec.size() - 1);
    }

    // 私有辅助方法，处理具体排序逻辑，带左右边界索引
    private static void quickSortHelper(MyVector vec, int left, int right) {
        if (left >= right) {
            return;
        }
        // 选取区间中间元素作为基准
        int pivot = (int) vec.elementAt((left + right) / 2);
        int i = left - 1;
        int j = right + 1;

        while (true) {
            // 找到左边第一个大于等于基准的元素
            while ((int) vec.elementAt(++i) < pivot);
            // 找到右边第一个小于等于基准的元素
            while ((int) vec.elementAt(--j) > pivot);

            // 索引交叉则退出循环
            if (i >= j) {
                break;
            }
            // 交换vec中两个索引位置的元素
            swap(vec, i, j);
        }

        // 递归处理左右两个分区
        quickSortHelper(vec, left, j);
        quickSortHelper(vec, j + 1, right);
    }

    // 修改swap方法，直接操作MyVector的元素
    private static void swap(MyVector vec, int i, int j) {
        Object temp = vec.elementAt(i);
        vec.setElementAt(vec.elementAt(j), i);
        vec.setElementAt(temp, j);
    }
}

修复说明 #

1. 新增边界辅助方法：用left和right标记当前排序的区间，直接操作原vec，不再依赖空向量。
2. 修复索引越界：i从left-1开始、j从right+1开始，通过++i和--j先移动再判断，避免一开始访问非法索引。
3. 实现有效交换：swap方法接收MyVector和索引，直接修改vec内部的元素，解决值传递的无效问题。
4. 正确递归分区：递归时传递原vec和划分后的左右区间，真正处理待排序的部分。

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