快速排序Partition方法故障排查：死循环与数组越界问题

代码中的核心问题： #

• 边界初始化错误：tooSmallIndex 初始化为 n-1 完全错误，待分区的数组是从 first 起始的连续 n 个元素，右边界应为 first + n - 1，否则会访问数组的非法位置，触发越界异常。
• 指针移动方向颠倒：
  • 寻找大于pivot的元素时，tooBigIndex 应从左往右递增，但代码中写的是 tooBigIndex--，会导致指针左移超出左边界，直接陷入死循环。
  • 寻找小于等于pivot的元素时，tooSmallIndex 应从右往左递减，但代码中写的是 tooSmallIndex++，会导致指针右移超出右边界，触发越界异常。
• 元素交换逻辑错误：交换两个指针位置的元素时，错误地将临时值赋值给 data[tooBigIndex + 1]，正确操作是直接交换 data[tooBigIndex] 和 data[tooSmallIndex]。
• Pivot赋值错误：直接用 data[tooSmallIndex] = pivot 会覆盖该位置原有元素，正确做法是交换原pivot所在的 data[first] 和 data[tooSmallIndex]，确保pivot最终落在正确分区点。

修正后的代码： #

private static int partition(int[] data, int first, int n)
    // Precondition: n > 1, and data has at least n elements starting at
    // data[first].
    // Postcondition: The method has selected some "pivot value" that occurs
    // in data[first]...data[first+n-1]. The elements of data have then been
    // rearranged and the method returns a pivot index so that
    //   -- data[pivot index] is equal to the pivot;
    //   -- each element before data[pivot index] is <= the pivot;
    //   -- each element after data[pivot index] is > the pivot.
{
    int tooBigIndex = first + 1;
    int pivot = data[first];
    // 修正右边界初始化
    int tooSmallIndex = first + n - 1;
            
    while (tooBigIndex <= tooSmallIndex) {
        // 修正指针移动方向：向右查找大于pivot的元素
        while (tooBigIndex <= first + n - 1 && data[tooBigIndex] <= pivot) {
            tooBigIndex++;
        }
        // 修正指针移动方向：向左查找小于等于pivot的元素
        while (data[tooSmallIndex] > pivot) {
            tooSmallIndex--;
        }
        if (tooBigIndex < tooSmallIndex) {
            // 修正交换逻辑：直接交换两个指针位置的元素
            int temp = data[tooBigIndex];
            data[tooBigIndex] = data[tooSmallIndex];
            data[tooSmallIndex] = temp;
        }
    }
    
    // 修正pivot位置：交换原pivot位置与tooSmallIndex位置的元素
    data[first] = data[tooSmallIndex];
    data[tooSmallIndex] = pivot;
    
    return tooSmallIndex;
}

内容的提问来源于stack exchange，提问作者Skyler Van Kleeck