Python实现不依赖排序库的稳定排序方法

Nice question! Your initial idea works but does have efficiency issues—let's break down why, then jump into a far better approach that's both fast and naturally preserves original order for same-length words.

Why Your Original Approach Is Slow #

Your plan of using a Counter to track length counts and then fetching words by length would likely require repeatedly scanning the original list to pick out matching words. That leads to O(n²) time complexity in the worst case (e.g., if every word has a unique length, you scan the list n times). Not ideal for larger datasets.

The Optimal Solution: Bucket Sort #

Bucket sort is perfect here because:

• It’s inherently stable (we’ll preserve original order for same-length words automatically)
• It runs in O(n + k) time (n = number of words, k = maximum word length) which is nearly linear and way faster than your initial idea.

Here’s how it works step by step:

1. Create "buckets" for each possible word length: Each bucket is a list that holds words of that length.
2. Fill buckets in original order: Iterate through your input list once, adding each word to the bucket matching its length. This ensures same-length words stay in their original sequence.
3. Concatenate buckets by length: Traverse the buckets from shortest to longest, appending all words in each bucket to your final result.

Code Implementation (Basic Bucket Sort) #

def stable_sort_by_length(words):
    if not words:
        return []
    
    # Find the longest word to know how many buckets we need
    max_length = max(len(word) for word in words)
    # Initialize buckets: index = word length, value = list of words
    buckets = [[] for _ in range(max_length + 1)]
    
    # Populate buckets while preserving original order
    for word in words:
        buckets[len(word)].append(word)
    
    # Build the result by combining buckets from shortest to longest
    sorted_words = []
    for bucket in buckets:
        sorted_words.extend(bucket)
    
    return sorted_words

# Test with your example
words = ['dog', 'cat', 'hello', 'girl', 'py', 'book']
print(stable_sort_by_length(words))  # Output: ['py', 'dog', 'cat', 'girl', 'book', 'hello']

Optimized Version (For Sparse Length Ranges) #

If your words have wildly varying lengths (e.g., some 2-letter words, some 100-letter words), creating buckets for every length up to 100 wastes space. Instead, use a dictionary to track only lengths that actually exist:

def stable_sort_by_length_optimized(words):
    if not words:
        return []
    
    # Map each length to its list of words (preserving original order)
    length_groups = {}
    for word in words:
        length = len(word)
        if length not in length_groups:
            length_groups[length] = []
        length_groups[length].append(word)
    
    # Sort the unique lengths, then combine their word lists
    sorted_lengths = sorted(length_groups.keys())
    sorted_words = []
    for length in sorted_lengths:
        sorted_words.extend(length_groups[length])
    
    return sorted_words

This version runs in O(n + k log k) time, where k is the number of unique lengths. Since k is almost always small compared to n, this is still extremely efficient.

Why This Works for Stability #

By adding words to buckets in the exact order they appear in the input list, same-length words stay in their original sequence. When we concatenate the buckets, that order is preserved—no extra work needed to maintain stability.

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