插入排序平均时间复杂度：实例推导与公式不符的疑问

Hey there! Let's unpack why your manual calculation of insertion sort's average-case performance might be clashing with the standard formula—this is a super common pitfall, so you’re not alone in this confusion.

First, let’s quickly validate your code: it’s correct (aside from a tiny typo in the array initialization: {1, 2 3, 4} should be {1, 2, 3, 4}). The logic follows standard insertion sort: iterate through the array, take each element, and shift larger preceding elements right until you find the correct position to insert the current element.

Now, let’s get to the heart of the discrepancy. The most likely reasons your manual results don’t match the standard average-case formula are:

1. You’re not averaging over all possible permutations #

The standard average-case analysis for insertion sort assumes we’re averaging performance across all n! possible permutations of the input array. If you’re only testing a handful of cases (like the sorted array [1,2,3,4], reverse-sorted [4,3,2,1], or a few partial cases), you’re not capturing the true average.

For example:

• The sorted array requires 0 shifts and 3 comparisons (one for each element after the first, no loops entered).
• The reverse-sorted array requires 6 shifts and 6 comparisons (each element has to shift all preceding elements).
• But most permutations fall somewhere in between—like [2,1,4,3] (1 shift, 2 comparisons) or [3,1,4,2] (3 shifts, 4 comparisons).

2. You might be miscalculating comparison/shift counts #

Insert sort’s operations are easy to miscount:

• Comparisons: The while loop’s condition counts as a comparison every time it runs—even when the condition fails (e.g., when you hit an element smaller than the key, you still compare once before exiting the loop).
• Shift direction: We compare elements from right to left (starting at i-1 and moving backward), not left to right. This means you don’t always compare all preceding elements—if you hit a smaller element early, you stop. For example, in [3,4,1,2], inserting the 2 only requires 1 comparison (since 1 < 2 is checked first, no need to look at 3 or 4).

3. Clarifying the standard formula #

The standard average-case results for insertion sort (for n elements) are:

• Average number of comparisons: ~n²/4 (exact value is (n² + n - 2)/4 for 1-based indexing)
• Average number of shifts: ~n²/4 (exact value is (n² - n)/4)

For n=4:

• Exact average comparisons: (16 + 4 - 2)/4 = 4.5
• Exact average shifts: (16 - 4)/4 = 3

If you calculate the total comparisons across all 24 permutations of 4 elements and divide by 24, you’ll land right at 4.5—this matches the formula perfectly.

How to verify this yourself #

To check, pick a random set of permutations and calculate their comparison/shift counts:

• Take [2,3,1,4]: Inserting 3 (1 comparison, 0 shifts), inserting 1 (2 comparisons, 2 shifts), inserting 4 (1 comparison, 0 shifts). Total: 4 comparisons, 2 shifts.
• Take [4,1,3,2]: Inserting 1 (1 comparison, 1 shift), inserting 3 (2 comparisons, 1 shift), inserting 2 (2 comparisons, 2 shifts). Total:5 comparisons,4 shifts.

Averaging these with other permutations will quickly converge to the formula’s values.

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