Python手写冒泡排序报错列表索引越界，请求问题分析与解决

Hey Scott, let's walk through what's going wrong with your bubble sort code and fix it up step by step!

1. The "List Index Out of Range" Root Cause #

Your outer loop runs for i in range(length), which means when i reaches the last index of the list (length-1), trying to access alist[i+1] will go beyond the list's bounds (since list indices start at 0 and end at length-1).

Bubble sort only needs length-1 total passes to fully sort the list—each pass moves the next largest unsorted element to its correct position at the end.

2. Problematic Element Swapping #

Using alist.index(first) and alist.index(second) to get swap indices is risky:

• If your list has duplicate values, index() will only return the first occurrence of that value, leading to incorrect swaps.
• You already have the exact indices (i and i+1) from your loop—no need to call an extra method to find them!

3. Incomplete Bubble Sort Logic #

Bubble sort requires nested loops:

• The outer loop controls how many passes we make over the list.
• The inner loop handles comparing adjacent elements and swapping them if needed. Plus, each pass can skip the already sorted elements at the end of the list.

Corrected Bubble Sort Code #

Here's the fixed version with explanations:

data = [1, 32, 50, 12, 14, 7, 45, 27, 18, 9, 19, 22, 51, 42, 4, 25, 13, 6, 21, 49, 41, 37]
def bubbleSort(alist):
    # Make a copy of the input list to avoid modifying the original data
    sorted_list = alist.copy()
    length = len(sorted_list)
    
    # Outer loop: run length-1 passes (enough to sort the entire list)
    for i in range(length - 1):
        # Inner loop: compare elements up to the unsorted portion of the list
        # We subtract i because the last i elements are already sorted
        for j in range(length - 1 - i):
            # Swap adjacent elements if they're in the wrong order
            if sorted_list[j] > sorted_list[j + 1]:
                sorted_list[j], sorted_list[j + 1] = sorted_list[j + 1], sorted_list[j]
    
    return sorted_list

print(bubbleSort(data))

Bonus: Optimized Version #

We can add a flag to exit early if the list becomes sorted before all passes are done—this saves unnecessary iterations:

def bubbleSort(alist):
    sorted_list = alist.copy()
    length = len(sorted_list)
    
    for i in range(length - 1):
        swapped = False
        for j in range(length - 1 - i):
            if sorted_list[j] > sorted_list[j + 1]:
                sorted_list[j], sorted_list[j + 1] = sorted_list[j + 1], sorted_list[j]
                swapped = True
        # No swaps means the list is already sorted—exit early!
        if not swapped:
            break
    
    return sorted_list

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