仅使用while循环实现C#版Quick Sort的算法错误排查求助

Hey there! Let's work through your quicksort implementation issue together. I’ve gone through your code and found a couple of critical mistakes that are messing up the pivot placement—let’s break them down clearly.

Core Problem in the partition Function #

The biggest issue is in the final pivot swap step and return value:

• Right now, you’re swapping the pivot with i+1 and returning i+1, but this is incorrect. Let’s clarify what i represents when the outer while (i < j) loop ends:
  • i will land on the first element that’s greater than the pivot (or coincide with j if all elements up to that point are sorted relative to the pivot).
  • All elements to the left of i are ≤ pivot, and elements from i onwards (excluding the pivot itself) are > pivot.

So the pivot should be swapped with i (not i+1) to slot it into its correct sorted position. We also need an extra check to handle edge cases where all elements are ≤ the pivot.

Corrected Code for partition #

Here’s the fixed version of your partition function, with comments explaining the changes:

public static int partition(int[] a, int start, int end)
{
    int pivot = a[end];
    int i = start;
    int j = end - 1;

    while (i < j)
    {
        // Move i right until we find an element > pivot
        while (i < j && a[i] <= pivot)
            i++;
        // Move j left until we find an element ≤ pivot
        while (i < j && a[j] > pivot)
            j--;
        swap(a, i, j);
    }

    // Final pivot placement: handle two edge cases
    if (a[i] > pivot)
    {
        // i is the first position with element > pivot—swap here
        swap(a, i, end);
        return i;
    }
    else
    {
        // All elements up to i are ≤ pivot—place pivot after i
        swap(a, i + 1, end);
        return i + 1;
    }
}

Why This Fix Works #

Let’s test this with your sample array {9, 1, 4, 7, 3}:

1. After the outer loop ends, i=1 (pointing to 9, the first element greater than pivot 3).
2. We swap i with the pivot’s position (4), turning the array into {1, 3, 4, 7, 9}—which is correctly partitioned.
3. The function returns 1 as the pivot’s index, and the recursive calls will sort the left (empty) and right subarrays properly.

Bonus Note #

Your inner while loop logic (checking a[i] <= pivot and a[j] > pivot) is actually correct—it’s okay to leave equal elements on the left side of the pivot, as this doesn’t break the quicksort logic.

备注：内容来源于stack exchange，提问作者Inbar Manor