Java版首元素为基准的快速排序出现数组越界错误，求排查

问题场景 #

实现了以首个元素为基准的快速排序Java版本，测试数组{1,2,3,5,4}时，前三次递归正常，当基准值为5时触发数组越界异常，但相同逻辑的C++版本运行正常。

Java实现代码 #

class QuickSort {
    static int partition(int a[], int lb, int ub) {

        int start = lb;
        int end = ub;
        int pivot = a[lb];
        while (start < end) {
            while (pivot >= a[start])
                start++;
            while (a[end] > pivot)
                end--;
            if (start < end) {
                int temp = a[start];
                a[start] = a[end];
                a[end] = temp;
            }
        }
        int temp = a[end];
        a[end] = a[lb];
        a[lb] = temp;
        return end;
    }

    static void quickSort(int a[], int lb, int ub) {
        if (lb < ub) {
            int pivot = partition(a, lb, ub);
            quickSort(a, lb, pivot - 1);
            quickSort(a, pivot + 1, ub);
            
        }

    }

    public static void main(String[] args) {
        int a[] = { 1,2,3,5,4 };
        quickSort(a, 0, a.length - 1);
        for(int i=0;i<a.length;i++)
            {
                System.out.print(a[i]+" ");
            }
    }
}

异常信息 #

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5
at QuickSort.partition(QuickSort.java:11)
    at QuickSort.quickSort(QuickSort.java:29)
    at QuickSort.main(QuickSort.java:45)

正常运行的C++版本代码 #

#include <iostream>
#include <algorithm>
using namespace std;

int partition(int arr[], int low, int high)
{
    int i = low;
    int j = high;
    int pivot = arr[low];
    while (i < j)
    {
        while (pivot >= arr[i])
            i++;
        while (pivot < arr[j])
            j--;
        if (i < j)
            swap(arr[i], arr[j]);
    }
    swap(arr[low], arr[j]);
    return j;
}

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

void printArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main()
{
    int arr[] = {1,2,3,5,4};
    int size = sizeof(arr) / sizeof(int);
    cout<<"Before Sorting"<<endl;
    printArray(arr, size);
    quickSort(arr, 0, size - 1);
    cout<<"After Sorting"<<endl;
    printArray(arr, size);
    return 0;
}

问题根源 #

Java代码中partition方法的第一个while循环缺少边界限制：

while (pivot >= a[start])
    start++;

当基准值pivot是当前区间的最大值时（比如递归到区间[3,4]，元素为5和4，pivot=5），start会持续自增，直到超过区间上限ub（即4），变成5，此时访问a[start]就会触发数组越界异常。

C版本看似逻辑相同，但C对数组越界的检查不严格（属于未定义行为），即使i超出high也可能不会立刻崩溃，而Java会严格校验数组索引范围，直接抛出异常。

修复方案 #

给第一个while循环添加start <= ub的边界限制，确保start不会超出数组有效索引范围：

while (start <= ub && pivot >= a[start])
    start++;

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