C#排序循环无法对数组首个元素排序的问题求助

Hi there! No worries about formatting for your first post—let's get your sorting issue sorted out, and clarify that time complexity question too.

Why Your First Element Isn't Sorting Correctly #

Looking at your code, the key problem is how you're resetting i after a swap. When you set i = 0 inside the if block, the for loop's built-in i++ runs immediately after the loop body finishes. That means the next iteration starts with i = 1, not 0—so you never re-check the first element against the second one after that initial reset.

For example, if your array reaches [3, 1, 2, 5], the loop starts at i=0, sees 3 > 1, swaps them to [1, 3, 2, 5], sets i=0... but then the i++ kicks in, so the next iteration starts at i=1. If no swap happens at i=1 or later, the loop never circles back to confirm the first element is in the right spot.

The Fix #

Instead of setting i = 0, set i = -1. That way, when the for loop runs i++ next, it will start at 0 again, letting you re-check the entire array from the beginning after every swap:

for (int i = 0; i < array.Length; i++) {
    if(i != array.Length - 1 && array[i] > array[i + 1]) {
        int lowerValue = array[i + 1];
        int higherValue = array[i];
        array[i] = lowerValue;
        array[i + 1] = higherValue;
        i = -1; // Reset to -1 so next i++ brings us back to 0
    }
}

Alternatively, a cleaner, more readable approach uses a flag to track swaps (the standard bubble sort pattern):

bool swapped;
do {
    swapped = false;
    for (int i = 0; i < array.Length - 1; i++) {
        if (array[i] > array[i + 1]) {
            // Swap elements
            int temp = array[i];
            array[i] = array[i + 1];
            array[i + 1] = temp;
            swapped = true;
        }
    }
} while (swapped);

This loops through the array until no more swaps are needed—no messy i resets required.

Time Complexity Breakdown #

Your initial guess about linear complexity is off, and it's definitely not exponential (that's for problems like unmemoized recursive Fibonacci, where operations grow exponentially with input size).

Your code is a variant of bubble sort, which has a worst-case and average time complexity of O(n²). Here's why:

• In the worst case (e.g., a completely reversed array), you'll need to traverse the array n times (once for each element to "bubble" it into its correct position).
• Each traversal checks roughly n elements.
• Multiplying these gives you O(n * n) = O(n²).

Even with the i = 0 reset, you're still doing a fixed number of passes relative to n—no exponential growth here.

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