ArrayList版QuickSort三种pivot实现问题求助：仅末尾元素法正常运行

Hey there! Let’s work through those pivot selection bugs you’re hitting with your ArrayList-based QuickSort. I’ve debugged similar issues plenty of times, so let’s break down the most common pitfalls for each problematic pivot method.

1. Random Element Pivot Problems #

The #1 mistake here is usually not swapping the random pivot to a fixed position (like the end) before running your partition logic. Most basic QuickSort implementations assume the pivot is at the end of the subarray—if you pick a random element but leave it in place, your partition code will still treat the last element as the pivot, leading to incorrect sorting.

Fix Example: #

import java.util.Collections;
import java.util.Random;

// Inside your quickSort method, when selecting random pivot:
Random rand = new Random();
int pivotIndex = rand.nextInt(high - low + 1) + low; // Pick index within [low, high]
// Swap the random pivot to the end of the subarray to match your working partition logic
Collections.swap(arr, pivotIndex, high);
// Now proceed with your existing partition code (which uses arr.get(high) as pivot)

Also double-check that your recursive calls use the correct pivot position returned by the partition function, not the original random index you picked.

2. Median-of-Three Pivot Problems #

Median-of-three has a few common gotchas:

• Incorrect median calculation: Failing to properly compare the first, middle, and last elements to find the true median.
• Not swapping the median to the partition’s expected position: Just like the random pivot, if your partition expects the pivot at the end, you need to move the median there first.
• Off-by-one errors in middle index: Using (low + high)/2 can cause integer overflow for very large arrays (unlikely with ArrayLists, but still risky) or return an index outside your subarray bounds.

Fix Example for Median-of-Three: #

First, a helper to find the median index correctly:

private static int medianOfThree(ArrayList<Integer> arr, int low, int high) {
    int mid = low + (high - low) / 2; // Safe way to calculate middle without overflow
    
    // Compare the three elements to find the median index
    if ((arr.get(low) >= arr.get(mid) && arr.get(low) <= arr.get(high)) || 
        (arr.get(low) <= arr.get(mid) && arr.get(low) >= arr.get(high))) {
        return low;
    } else if ((arr.get(mid) >= arr.get(low) && arr.get(mid) <= arr.get(high)) || 
               (arr.get(mid) <= arr.get(low) && arr.get(mid) >= arr.get(high))) {
        return mid;
    } else {
        return high;
    }
}

Then use it in your QuickSort:

int pivotIndex = medianOfThree(arr, low, high);
Collections.swap(arr, pivotIndex, high); // Move median to end for partition
int partitionPos = partition(arr, low, high); // Your existing partition method
quickSort(arr, low, partitionPos - 1);
quickSort(arr, partitionPos + 1, high);

General Debugging Tips #

• Add debug prints: Log the pivot value, its index, and the state of the ArrayList right after selecting/swapping the pivot. This will show you if the pivot is where you expect it to be.
• Test small arrays: Run your code with tiny test cases (e.g., [3,1,4,2]) and step through with a debugger to see exactly where the partition or recursion goes wrong.
• Check for index out-of-bounds: Make sure your random pivot selection uses rand.nextInt(high - low + 1) + low instead of rand.nextInt(arr.size())—this keeps the index within the current subarray bounds.

If you can share snippets of your actual pivot selection and partition code, we can pinpoint the exact issue even faster!

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