我最初僅使用如何提高我在python中的快速排序數據透視選擇?
pivots = random.randrange(l,r)
這裏L和R給出一個隨機的支點將是定義我的整數範圍
我希望通過大幅增加可能罩,爲了提高運行時間我樞軸將是通過選擇三個隨機樞軸的中位數的一個好樞軸。以下是我使用的代碼,它使我的運行時間增加了20%-30%。
rr = random.randrange
pivots = [ rr(l,r) for i in range(3) ]
pivots.sort()
如何實現上述要快得多?加入下面
import random
def quicksort(array, l=0, r=-1):
# array is list to sort, array is going to be passed by reference, this is new to me, try not to suck
# l is the left bound of the array to be acte on
# r is the right bound of the array to act on
if r == -1:
r = len(array)
# base case
if r-l <= 1:
return
# pick the median of 3 possible pivots
#pivots = [ random.randrange(l,r) for i in range(3) ]
rr = random.randrange
pivots = [ rr(l,r) for i in range(3) ]
pivots.sort()
i = l+1 # Barrier between below and above piviot, first higher element
array[l], array[pivots[1]] = array[pivots[1]], array[l]
for j in range(l+1,r):
if array[j] < array[l]:
array[i], array[j] = array[j], array[i]
i = i+1
array[l], array[i-1] = array[i-1], array[l]
quicksort(array, l, i-1)
quicksort(array, i, r)
return array
編輯2整個代碼: 這是校正代碼由於
編輯。有沒有在算法挑選3個樞軸
import random
def quicksort(array, l=0, r=-1):
# array is list to sort, array is going to be passed by reference, this is new to me, try not to suck
# l is the left bound of the array to be acte on
# r is the right bound of the array to act on
if r == -1:
r = len(array)
# base case
if r-l <= 1:
return
# pick the median of 3 possible pivots
mid = int((l+r)*0.5)
pivot = 0
#pivots = [ l, mid, r-1]
if array[l] > array[mid]:
if array[r-1]> array[l]:
pivot = l
elif array[mid] > array[r-1]:
pivot = mid
else:
if array[r-1] > array[mid]:
pivot = mid
else:
pivot = r-1
i = l+1 # Barrier between below and above piviot, first higher element
array[l], array[pivot] = array[pivot], array[l]
for j in range(l+1,r):
if array[j] < array[l]:
array[i], array[j] = array[j], array[i]
i = i+1
array[l], array[i-1] = array[i-1], array[l]
quicksort(array, l, i-1)
quicksort(array, i, r)
return array
這聽起來不可思議。爲什麼你的支點會更好,如果你取三個隨機樞紐的中位數? –
我們需要查看代碼的其餘部分。 – Kevin
你的樞軸選擇真的很奇怪...不應該將樞軸作爲排序列表的一個元素(大概是'l')嗎? – mgilson