写法 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)
1
Alpacino OP 这两个写法有什么区别吗?
是处理 edge case 上的不同? |
2
billc 2019-07-16 15:14:24 +08:00
茴香豆的茴有 4 种写法。
-------------------------------------------- 正经回答: 没差别,你把下面所有的 i,替换成 i-1,和上面的完全一样 |