基于列表切片的快速排序代码错误排查及修正请求

Hey there, let's figure out why your slice-based quicksort is giving wrong results and fix it step by step.

What's Causing the Wrong Output? #

The core issues are two-fold:

1. Slices create new list objects: When you do a1 = a[0:pivot] and a2 = a[pivot+1:], these are brand new lists—not references to the original a's subarrays. So when you recursively sort a1 and a2, you're modifying these new lists, not the original array. Your result function tries to copy sorted values back, but it has a critical loop logic error.

2. Bug in the result function: The second loop uses range(pivot+1, len(a2)) as target indices in a, which is totally incorrect. len(a2) is the length of the sliced subarray, not the original array. This means you're not covering all positions from pivot+1 to the end of a, leading to un-updated or incorrectly overwritten elements (like the duplicate 92 in your output).

Fixed Code (Clean, Non-Mutating Style) #

Instead of patching values back into the original array with a clunky result function, we can leverage slice behavior directly: recursively sort the subarrays and return the combined sorted list (left sorted + pivot + right sorted). This eliminates the loop bug and makes the code cleaner.

def partition(a):
    length = len(a)
    if length == 0:
        return 0
    c = 0
    piv = a[0]
    # Count elements smaller than the pivot
    for i in range(length):
        if a[i] < piv:
            c += 1
    # Move pivot to its correct partition position
    a[c], a[0] = a[0], a[c]
    piv_idx = c
    i = 0
    j = length - 1
    # Partition remaining elements
    while i < j:
        if a[i] < a[piv_idx]:
            i += 1
        elif a[j] > a[piv_idx]:
            j -= 1
        else:
            a[i], a[j] = a[j], a[i]
            i += 1
            j -= 1
    return piv_idx

def quick_sort(a):
    le = len(a)
    if le <= 1:
        return a
    # Create a copy to avoid modifying the original input list during partition
    arr_copy = a.copy()
    pivot_idx = partition(arr_copy)
    # Recursively sort left and right subarrays
    left_sorted = quick_sort(arr_copy[:pivot_idx])
    right_sorted = quick_sort(arr_copy[pivot_idx+1:])
    # Combine sorted parts with the pivot
    return left_sorted + [arr_copy[pivot_idx]] + right_sorted

# Test the code
a = [100,98,93,96,99,92,91]
res = quick_sort(a)
print(res)  # Output: [91, 92, 93, 96, 98, 99, 100]

Key Changes: #

• Removed the result function entirely—we now return the combined sorted list directly.
• Added a copy of the input array in quick_sort before calling partition to keep the function pure (it returns a new sorted list instead of mutating the input).
• Simplified the base case to if le <=1: return a since lists of length 0 or 1 are already sorted.

Fixed Code (In-Place Style) #

If you prefer modifying the original array in-place instead of returning a new list, here's how to fix your original result function:

def partition(a):
    length=len(a)
    if length ==0:
        return 0
    c=0
    piv=a[0]
    for i in range(0,length):
        if a[i]<piv:
            c+=1
    a[c],a[0]=a[0],a[c]
    piv=c
    i=0
    j=length-1
    while i<j:
        if a[i]<a[piv]:
            i=i+1
        elif a[j]>a[piv]:
            j=j-1
        else:
            a[i],a[j]=a[j],a[i]
            i=i+1
            j=j-1
    return piv

def result(a1,a2,a,pivot):
    # Update left part with sorted a1
    for i in range(pivot):
        a[i] = a1[i]
    # Update right part with sorted a2 (fixed loop range)
    j = 0
    # Correct range: cover all positions from pivot+1 to end of original array
    for i in range(pivot+1, len(a)):
        a[i] = a2[j]
        j +=1

def quick_sort(a):
    le=len(a)
    if le==1 or le==0:
        return
    pivot=partition(a)
    a1=a[0:pivot]
    a2=a[pivot+1:]
    quick_sort(a1)
    quick_sort(a2)
    result(a1,a2,a,pivot)

a=[100,98,93,96,99,92,91]
quick_sort(a)
print(a)  # Output: [91, 92, 93, 96, 98, 99, 100]

The fix here is in the result function's second loop: we use range(pivot+1, len(a)) instead of range(pivot+1, len(a2)) to ensure we cover all positions from the pivot's right to the end of the original array.

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