关于快排 quicksort 的两种写法

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1957 天前的主题，其中的信息可能已经有所发展或是发生改变。

写法 1 i = low 返回 low

def partition(arr,low,high): 
    i = low      # index of smaller element 
    pivot = arr[high]     # pivot
    for j in range(low , high): 
        if   arr[j] <= pivot:
            arr[i],arr[j] = arr[j],arr[i] 
            i = i+1
    arr[i],arr[high] = arr[high],arr[i] 
    return i

def quickSort(arr,low,high): 
    if low < high: 
        pi = partition(arr,low,high) 
        quickSort(arr, low, pi-1) 
        quickSort(arr, pi+1, high)

写法 2 i = (low-1)开始返回 i + 1

def partition(arr,low,high): 
    i = ( low-1 )         # index of smaller element 
    pivot = arr[high]     # pivot 
  
    for j in range(low , high): 
        if   arr[j] <= pivot: 
            i = i+1 
            arr[i],arr[j] = arr[j],arr[i] 
  
    arr[i+1],arr[high] = arr[high],arr[i+1] 
    return ( i+1 ) 
  
def quickSort(arr,low,high): 
    if low < high: 
        pi = partition(arr,low,high) 
        quickSort(arr, low, pi-1) 
        quickSort(arr, pi+1, high)

2 条回复 • 2019-07-16 15:14:24 +08:00

Alpacino

2019-07-16 12:32:29 +08:00

这两个写法有什么区别吗？
是处理 edge case 上的不同？

billc

2019-07-16 15:14:24 +08:00

茴香豆的茴有 4 种写法。

--------------------------------------------

正经回答：
没差别，你把下面所有的 i，替换成 i-1，和上面的完全一样