求助：递归实现偶数前置、奇偶各自升序的数组排序问题

Got it, let's fix that issue with your array sorting. The goal is to have all sorted evens upfront, followed by sorted odds, and we need to do this recursively. Let's walk through the approach and code.

Key Recursive Strategy #

The idea is to break the problem into smaller chunks with recursion:

• Base Case: If the input array is empty, return an empty array—this is our stopping point.
• Recursive Step:
  1. Grab the first element of the array.
  2. Recursively sort the rest of the array.
  3. Insert the first element into the correct position in the recursively sorted result:
     • If it's even, place it in the sorted evens section (keeping them in ascending order).
     • If it's odd, place it in the sorted odds section (also ascending).

Working Code (Python) #

def sort_evens_before_odds(arr):
    # Base case: empty array has nothing to sort
    if not arr:
        return []
    
    current_num = arr[0]
    # Recursively process the rest of the array first
    sorted_rest = sort_evens_before_odds(arr[1:])
    
    # Split the recursively sorted result into evens and odds
    evens_part = []
    odds_part = []
    for num in sorted_rest:
        if num % 2 == 0:
            evens_part.append(num)
        else:
            odds_part.append(num)
    
    # Insert current number into the correct sorted section
    if current_num % 2 == 0:
        # Insert into evens in ascending order
        inserted = False
        for idx in range(len(evens_part)):
            if current_num < evens_part[idx]:
                evens_part.insert(idx, current_num)
                inserted = True
                break
        if not inserted:
            evens_part.append(current_num)
    else:
        # Insert into odds in ascending order
        inserted = False
        for idx in range(len(odds_part)):
            if current_num < odds_part[idx]:
                odds_part.insert(idx, current_num)
                inserted = True
                break
        if not inserted:
            odds_part.append(current_num)
    
    # Combine the sorted evens and odds and return
    return evens_part + odds_part

# Test your problematic case
test_arr = [10,9,8,7,6,5,4,3,2,1]
print(sort_evens_before_odds(test_arr))  # Output: [2,4,6,8,10,1,3,5,7,9]

# Test the sample input
sample_input = [1,2,3,4,5]
print(sort_evens_before_odds(sample_input))  # Output: [2,4,1,3,5]

How This Fixes Your Issue #

Your previous output was a full ascending sort, which didn't separate evens and odds. This recursive approach ensures:

1. We always keep evens and odds in distinct sections.
2. Each section stays in ascending order by inserting each element into the correct position during the recursive unwinding.
3. The recursion builds up the sorted array one element at a time, guaranteeing every number ends up in the right spot.

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